题目描述

すぬけ君はパン屋の経営者です． 彼はこれから $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-($職人を雇うのに使った費用の合計$)$ を最大化したいです． この最大値を求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$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

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

提示

制約

• $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$
• 入力される値はすべて整数

Sample Explanation 1

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

Sample Explanation 2

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