← 返回题目列表

AtCoder · kupc2019_f

F. 和真王国的没落

中文机器翻译题面 查看原题

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

注意溢出。