材料结算（material）

题目描述

某工厂正在执行一批特殊加工任务。

工厂记录了连续 (m) 天的材料消耗标准，第 (i) 天的消耗标准为 $(a_i)$。

共有 (n) 个候选加工任务。

第 (i) 个任务对应一个日期区间 $(L_i,R_i)$，完成后可以获得 (v_i) 的收益。

一个任务需要消耗的材料数量，等于该日期区间内每天材料消耗标准之和。

每个任务最多执行一次。

所有任务相互独立，即使日期区间重叠也可以同时执行，材料消耗分别计算。

现在工厂要求：所有被选择任务的材料消耗总量必须恰好等于 (V)。

请计算满足条件时可以获得的最大总收益。

如果不存在满足要求的任务选择方案，输出 -1。

输入格式

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

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

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

输出格式

输出最大总收益，无解输出 -1。

输入输出样例 #1

输入

5 4 8
2 3 4 1 2
1 2 5
3 4 7
2 3 8
4 5 4

输出

11

样例解释

各任务的材料消耗分别为 5、5、7、3。

可以选择第 2 个与第 4 个任务：

总消耗为 (5+3=8)。

总收益为 (7+4=11)。

数据范围

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