AT_arc137_e [ARC137E] Bakery

[problemUrl]: https://atcoder.jp/contests/arc137/tasks/arc137_e すぬけ君はパン屋の経営者です． 彼はこれから $ 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 $

答えを出力せよ．

### 制約 - $ 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 職人を一人も雇わないのが最適です．