E - Bakery Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ．

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

Score : 800 points

Problem Statement

Snuke runs a bakery. He is planning for the next N days. Let us call these days Day 1,2,\cdots,N.

At the moment, the bakery hires nobody. There are M bakers that Snuke can hire, numbered 1 to M.

C_i yen must be paid to hire Baker i. If Baker i is hired, they will work on Day L_i, L_i+1, \cdots, R_i, baking one loaf of bread each day.

For each j (1 \leq j \leq N), there is a limit A_j to the number of loaves of bread that can be sold on Day j. If x_j loaves of bread are baked on Day j, \min(x_j, A_j) loaves will be sold on that day.

Each loaf of bread sold will yield a profit of D yen.

Snuke wants to choose the set of bakers to hire to maximize the final profit: (The total number of loaves sold) \times D - (The total cost of hiring bakers). Find the maximum possible value of this.

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

11

Snuke should hire Baker 1, 3, 4. In this case, the total cost to hire bakers is 7, and the number of loaves baked on Day 1, 2, \cdots, N will be 1,1,0,1,1,2,1, respectively. A total of 6 loaves will be sold, for a final profit of 6 \times 3-7=11.

Sample Input 2

3 1 5
1 1 1
2 2 10

Sample Output 2

0

It is optimal to hire no baker.

Sample Input 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

Sample Output 3

543