問題文

カズマ王国には 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

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

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