题目描述

すぬけ君是一家面包店的老板。他正在为接下来的 $N$ 天制定营业计划。我们将这些天分别称为第 $1,2,\cdots,N$ 天。

目前，这家店还没有任何面包师。现在有 $M$ 位面包师候选人，编号为 $1$ 到 $M$。

雇佣第 $i$ 位面包师需要支付 $C_i$ 日元。如果雇佣了第 $i$ 位面包师，他将在第 $L_i,L_i+1,\cdots,R_i$ 天工作，并且每天制作 $1$ 个面包。

对于每一天 $j$（$1\leq j\leq N$），第 $j$ 天最多能卖出的面包数量为 $A_j$。如果第 $j$ 天制作了 $x_j$ 个面包，那么当天能卖出的面包数量为 $\min(x_j, A_j)$。

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

すぬけ君希望通过合理选择要雇佣的面包师集合，使得最终利润 $=$(卖出的面包总数)$\times D-$(雇佣面包师的总花费) 最大。请你求出这个最大值。

输入格式

输入以如下格式从标准输入读入。

$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

输出

11

样例 2

输入

3 1 5
1 1 1
2 2 10

输出

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

输出

543

说明/提示

限制条件

• $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$
• 所有输入的值均为整数。

样例解释 1

雇佣第 $1,3,4$ 位面包师即可。此时，雇佣面包师的总花费为 $7$。第 $1,2,\cdots,N$ 天分别制作的面包数量为 $1,1,0,1,1,2,1$。卖出的面包总数为 $6$，最终利润为 $6\times 3-7=11$。

样例解释 2

一个面包师都不雇佣是最优的选择。

由 ChatGPT 4.1 翻译