描述

你拥有一艘非常漂亮的船，许多人希望在夏季租用它，你决定最大化利润。对于每个客户，你知道他想租船的天数以及一系列选择，每个选择包含金额和截止日期。截止日期是从某个时间起点开始计算的天数，只有当你能在截止日期前完成租船（即租船时间段结束于截止日期或之前），才能获得该选择的金额。

例如，你的朋友Jack想租船20天，其选择如下：

• 若截止日期为60天，则你需在第0到41天（60天-20天+1）之间将船租给他20天，可获得1000欧元；
• 若截止日期为70天，可获得800欧元。

若某个客户的选择无法帮助最大化利润，可忽略该客户。已知所有客户及其选择，且必须按客户提交请求的顺序处理租船事宜。

编写程序，计算你能获得的最大利润。

输入

输入来自标准输入。每个数据集格式如下：

• n - 客户数量（n ≤ 100）；
• 接下来n行，每行一个整数，表示每个客户想租船的天数（最多100天）；
• 所有客户的选择总数；
• 选择列表，格式为客户编号, 截止日期, 金额，其中client_id为1到n的正整数，deadline ≤ 100。

数据集之间用空行分隔。

输出

对每个数据集，输出一行最大利润。不同数据集的输出之间用空行分隔。

输入数据 1

3  
2  
2  
4  
4  
1 2 14  
3 4 25  
2 4 12  
3 3 10  

输出数据 1

26  

来源

东南欧，2002