F - カズマ王国の陥落 /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

カズマ王国には N 個の街があり、それぞれの街には 1 人の勇者がいます。

i (1 \leq i \leq N) 番目の街の勇者は合計して A_i 体までのモンスターを倒すことができます。

勇者は経験値が欲しいので、自分の街に来たモンスターはできるだけ多く倒します。

あなたは魔王で、M 個の拠点を支配下に置いています。

j (1 \leq j \leq M) 番目の拠点からは合計 B_j 体のモンスターを自由に L_j, L_j+1, ..., R_j 番目の街に派遣します。

その結果、勇者に倒されなかったモンスターの数だけカズマ王国にダメージを与えることができます。

カズマ王国に与えられる合計ダメージの最大値を求めてください。

制約

  • 入力はすべて整数である。
  • 1 \leq N \leq 3000
  • 1 \leq M \leq 3000
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_j \leq 10^9
  • 1 \leq L_j \leq R_j \leq N

入力

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

N
A_1 A_2 ... A_N
M
L_1 R_1 B_1
L_2 R_2 B_2
\vdots
L_M R_M B_M

出力

カズマ王国に与えられる合計ダメージの最大値を出力せよ。


入力例 1

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

出力例 1

7

次のように派遣するとカズマ王国に合計して 7 ダメージを与えることができます。

  • 1 番目の拠点から 5 体のモンスターを 2 番目の街に、2 体のモンスターを 3 番目の街にそれぞれ派遣します。
  • 2 番目の拠点から 4 体のモンスターを 2 番目の街に派遣します。
  • 3 番目の拠点から 3 体のモンスターをそれぞれ 3 番目の街に派遣します。

入力例 2

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

出力例 2

4

入力例 3

10
9 7 4 11 5 100 95 3 55 12
12
2 3 6
1 2 2
1 4 8
3 5 5
3 5 6
4 4 6
5 7 3
5 8 5
1 10 52
9 10 13
7 9 2
8 9 5

出力例 3

83

入力例 4

1
1
10
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

出力例 4

9999999999

オーバーフローに気をつけてください。