配点 : 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 派送至第th个城市。
因此,你可以对和真王国造成与英雄未击败的怪物数量相同的伤害。
求对和真王国造成的最大总伤害。
制約
- 所有输入均为整数。
- 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 派送至第th个城市。
- 3 基地 3 体内的每个怪物 3 派送至第th个城市。
入力例 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
注意溢出。