配点 : $800$ 点

問題文

すぬけ君はパン屋の経営者です． 彼はこれから $N$ 日間の営業計画を考えています． これらの日を Day $1,2,\cdots,N$ と呼ぶことにします．

現在，この店にはパン職人が一人もいません． 雇う職人の候補は $M$ 人おり，$1$ から $M$ までの番号がついています．

職人 $i$ を雇うためには，$C_i$ 円を支払う必要があります． 職人 $i$ を雇った場合，その職人は Day $L_i,L_i+1,\cdots,R_i$ に働き，それぞれの日に $1$ つのパンを作ります．

各 $j$ ($1 \leq j \leq N$) について，Day $j$ に売れるパンの個数の最大値 $A_j$ が定まっており， Day $j$ に作られたパンの個数を $x_j$ とすると，その日は $\min(x_j,A_j)$ 個のパンが売れます．

パンは一つ売れるごとに $D$ 円の利益が得られます．

すぬけ君は，雇う職人の集合を適切に決めることで，最終的な利益$=($売れたパンの個数の合計$)\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$

出力

答えを出力せよ．

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

11

職人 $1,3,4$ を雇えばよいです． この時，職人を雇うのにかかる費用の合計は $7$ です． また，Day $1,2,\cdots,N$ に作られるパンの個数はそれぞれ $1,1,0,1,1,2,1$ 個です． 売れるパンの個数の合計は $6$ であり，最終的な利益は $6 \times 3-7=11$ になります．

3 1 5
1 1 1
2 2 10

0

職人を一人も雇わないのが最適です．

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