問題文

すぬけ君はパン屋の経営者です． 彼はこれから $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$

出力

答えを出力せよ．

入力例 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

職人 $1,3,4$ を雇えばよいです． この時，職人を雇うのにかかる費用の合計は $7$ です． また，Day $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