生产调配（production）

题目描述

某工厂共有 (m) 天的基础生产成本，第 (i) 天的成本为 $(a_i)$。

工厂提供 (n) 种加工方案。

第 (i) 种加工方案由三个整数 $(L_i,R_i,v_i)$ 描述。

采用一次该方案，需要支付从第 (L_i) 天到第 (R_i) 天的基础生产成本之和，并可以获得 (v_i) 的收益。

工厂按照方案持续的天数制定以下生产规则：

• 如果方案持续的天数为奇数，该方案可以重复执行任意非负整数次。
• 如果方案持续的天数为偶数，该方案最多只能执行一次。

方案持续天数为$(R_i-L_i+1)$。

不同方案及多次执行相互独立，每执行一次都需要支付完整成本。

工厂总预算为 (V)，要求所有方案的总成本不超过 (V)。

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

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入

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

输出

20

样例解释

四种方案的实际成本和数量限制分别为：

一种最优方案是：

• 执行方案 1 一次；
• 执行方案 2 一次；
• 执行方案 3 一次。

总成本为 (3+3+3=9)，总收益为 (7+5+8=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)$