订单清单（orders）

题目描述

某加工厂需要安排一批生产订单。

工厂共有 (m) 天的基础加工费用，第 (i) 天的费用为 $(a_i)$。

现在有 (n) 笔订单，每笔订单由三个整数$(L_i,R_i,v_i)$ 描述。

其中：

• $(L_i) 表示订单对应的起始日期；$
• $(R_i) 表示订单对应的结束日期；$
• $(v_i) 表示完成这笔订单可以获得的收益$。

接受一笔订单，需要支付从第 (L_i) 天到第 (R_i) 天的所有基础加工费用之和。

每笔订单最多只能接受一次。

工厂的总预算为 (V)，要求所有被接受订单的总加工费用不超过 (V)。

不同订单之间相互独立，即使对应的日期区间存在重叠，也可以同时接受，但每笔订单的加工费用必须分别计算。

请计算工厂能够获得的最大总收益。

输入格式

第一行包含三个整数 (m,n,V)，分别表示天数、订单数量和总预算。

第二行包含 (m) 个正整数 $(a_1,a_2,\ldots,a_m)$，表示每天的加工费用。

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

输出格式

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

输入输出样例 #1

输入

6 4 10
2 1 3 2 4 1
1 2 4
3 4 8
5 6 7
2 5 14

输出

15

样例解释

四笔订单的加工费用分别为：

选择第 2、3 笔订单，总费用为 (5+5=10)，总收益为 (8+7=15)。

数据范围

• $(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)$