問題文
高桥喜欢一遍又一遍地观看同一类型的电影。连续观看同类型的电影可以让你获得更多的快乐。
然而,高桥很健忘,所以一旦他看了不同类型的电影,他就完全忘记了他以前看过的电影。即使您观看以前看过的电影,您也会获得与第一次观看该电影相同的幸福感,除了您之前看过的电影。
高桥君, 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