题目描述

Snuke经营一家面包店。他正在计划未来的 $N$ 天，我们将这些天称为第 $1,2,\\cdots,N$ 天。

目前，面包店没有雇佣任何人。有 $M$ 个面包师傅，编号为 $1$ 到 $M$。

雇佣面包师傅 $i$ 需要支付 $C_i$ 日元。如果雇佣了师傅 $i$，则他们将在第 $L_i, L_i+1, \\cdots, R_i$ 天工作，每天烤一个面包。

对于每个 $j$（$1 \\leq j \\leq N$），当天能够售卖的面包数量有上限 $A_j$。如果第 $j$ 天烤了 $x_j$ 个面包，则最多卖出 $\\min(x_j, A_j)$ 个面包。

每售出一个面包可以获得利润 $D$ 日元。

Snuke想要选择雇佣的面包师傅组合以最大化最终利润：$($售出的面包总数$) \\times D - ($雇佣面包师傅的总成本$)$。求出可能的最大值。

约束条件

• $1 \\leq N \\leq 2000$
• $1 \\leq M \\leq 2000$
• $1 \\leq D \\leq 10^9$
• $1 \leq A_j \leq M$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq C_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入以标准输入给出，格式如下：

$N$ $M$ $D$ $A_1$ $A_2$ $\\cdots$ $A_N$ $L_1$ $R_1$ $C_1$ $L_2$ $R_2$ $C_2$ $\\vdots$ $L_M$ $R_M$ $C_M$

输出

输出答案。

示例输入 1

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

示例输出 1

11

Snuke应该雇佣师傅 $1, 3, 4$。在这种情况下，雇佣师傅的总成本为 $7$，第 $1, 2, \\cdots, N$ 天烤出的面包数量分别是 $1,1,0,1,1,2,1$。总共卖出 $6$ 个面包，最终利润为 $6 \\times 3-7=11$。

示例输入 2

3 1 5
1 1 1
2 2 10

示例输出 2

0

最优解是不雇佣任何面包师傅。

示例输入 3

10 10 42
6 5 1 5 2 4 2 7 10 9
3 4 4
3 7 136
9 9 14
2 7 152
3 3 33
2 4 100
3 3 38
1 10 28
3 5 66
8 8 15

示例输出 3

543