← 返回题目列表

AtCoder · code_formula_2014_final_d

D. 连续观看电影

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

問題文

高桥喜欢一遍又一遍地观看同一类型的电影。连续观看同类型的电影可以让你获得更多的快乐。

然而,高桥很健忘,所以一旦他看了不同类型的电影,他就完全忘记了他以前看过的电影。即使您观看以前看过的电影,您也会获得与第一次观看该电影相同的幸福感,除了您之前看过的电影。

高桥君, k 当您连续观看同一类型的电影两次时, 获得 H_k 幸福。换句话说,连续观看同一类型的电影。 如果您观看 k次,您最终会得到 1 从第二次开始 你将获得 H_1 + H_2 + … + H_k幸福。

高桥君, k 连续观看两次同类型电影获得的幸福感 H_k 给定今天的电影时间表,求高桥今天通过看电影可以获得的最大幸福感。

请注意,无法中途开始或停止观看电影。

另外, 2 假设两部电影的播放时间没有重叠,即使两部电影之间没有空闲时间,也可以观看两部电影。


入力

输入将以以下格式从标准输入提供。

N
H_1 H_2 … H_N
M_1 S_1 E_1
M_2 S_2 E_2
:
M_N S_N E_N
  • 1 行包含一个整数,表示今天计划放映的电影数量。 给出了 N (1≦N≦3000) 。 来自行
  • 2 第几行包含,N 数字。其中 i (1≦i≦N) 第一个整数 H_i(1≦H_i≦10000) 是i 代表您连续观看一部电影时获得的幸福程度。
  • i<j 当时H_i≦H_j 得到保证。 从行
  • 3 开始,N 行表示有关今天计划放映的电影的信息。其中 代表第 i (1≦i≦N) 第几行包含,i 部电影类型的整数 M_i(1≦M_i≦N) ,表示演出开始和结束时间的整数 S_i, E_i(0≦S_i<E_i≦100000) 用空格分隔。

出力

高桥君计算今天能从电影中获得的最大幸福总和。 输出为 1 行。在输出末尾添加换行符。


入力例1

4
100 200 300 400
1 0 120
1 15 135
2 10 40
1 240 330

出力例1

300

1第部电影和 如果您观看第4部电影2连续类型 我决定看电影1,100 + 200 = 300幸福。


入力例2

10
100 200 250 250 300 400 540 600 650 680
1 10 130
2 0 900
1 20 110
1 200 230
3 200 210
2 201 220
2 240 300
3 0 90
1 250 320
2 330 400

出力例2

650