AT_arc137_e [ARC137E] Bakery

すぬけ君是一家面包店的老板。他正在为接下来的 $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\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 翻译