收益评估（evaluate）

题目描述

某研究中心计划采购一批实验设备。

研究中心记录了连续 (m) 天的实验评价数据，第 (i) 天的评价分数为$(a_i)。$

现在共有 (n) 台候选设备。

第 (i) 台设备具有三个属性：

• $(L_i)：对应的实验开始日期；$
• $(R_i)：对应的实验结束日期；$ -$(w_i)：设备所需的采购预算。$

一台设备能够产生的总使用价值，等于它对应日期区间内所有评价分数之和。

每台设备最多只能采购一次。

现有采购预算 (V)，要求所有选中设备的采购费用之和不超过 (V)。

不同设备可以使用重叠的实验日期，它们的使用价值分别计算，互不影响。

请计算可以获得的最大总使用价值。

输入格式

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

第二行包含 (m) 个整数 (a_i)，表示每天的评价分数。

接下来 (n) 行，每行包含三个整数：

L R w

输出格式

输出能够获得的最大总使用价值。

输入输出样例 #1

输入

6 4 7
3 2 4 1 5 2
1 2 3
3 5 4
2 4 3
5 6 2

输出

17

样例解释

四台设备的使用价值分别为：

例如，选择第 2、3 台设备，总采购费用为 (4+3=7)，总使用价值为 (10+7=17)。

数据范围

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