巡检安排（inspection）

题目描述

某研究基地需要安排一批巡检任务。

基地共有 (m) 天的巡检资源消耗标准，第 (i) 天的消耗标准为$(a_i)$。

现有 (n) 个候选巡检任务。

第 (i) 个任务由三个整数 $(L_i,R_i,v_i)$ 描述。

执行该任务，需要在从第 $(L_i) 天到第 (R_i)$天的每一天进行巡检。

任务消耗的资源数量为这些天的资源消耗标准之和，完成后可以获得 (v_i) 的收益。

基地只有一支巡检队，因此两个被选择的任务不能包含相同的日期。

也就是说，如果选择了两个不同的任务，它们对应的日期区间必须完全不重叠。

每个任务最多执行一次。

基地共有 (V) 单位资源，要求所有选择任务的总资源消耗不超过 (V)。

请计算可以获得的最大总收益。

输入格式

第一行包含三个整数 (m,n,V)。

第二行包含 (m) 个正整数 (a_i)。

接下来 (n) 行，每行包含三个整数 (L_i,R_i,v_i)。

输出格式

输出一个整数，表示最大总收益。

输入输出样例 #1

输入

6 5 11
2 1 3 2 1 2
1 2 5
2 4 9
3 4 8
5 6 7
4 5 6

输出

20

样例解释

可以选择第 1、3、4 个任务。

它们对应的日期区间分别为：

• 第 1 个任务：1,21,2
• 第 3 个任务：3,43,4
• 第 4 个任务：5,65,6

三个区间互不重叠。

资源消耗分别为 3、5、3，总消耗为 11。

总收益为 (5+8+7=20)。

数据范围

• $(1\le m\le10^5)$
• $(1\le n\le100)$
• $(1\le V\le2000)$
• $(1\le a_i\le1000)$
• $(1\le L_i\le R_i\le m)$
• $(1\le v_i\le10000)$