问题描述

高桥君非常喜欢多次看同一类型的电影。通过连续观看同一类型的电影，他可以获得更多的幸福感。

然而，由于高桥君健忘，一旦他观看了另一种类型的电影，他之前看过的电影就会完全被遗忘。即使再次看到以前看过的电影，除了最近观看的那一种类型外，他只能获得第一次看该类型电影时的幸福感。

当高桥君连续观看同一类型的电影 $k$ 次时，他可以获得 $H_k$ 的幸福感。换句话说，如果连续观看相同类型的电影 $k$ 次，那么他最后将获得从第一次观看到第 $k$ 次观看的总幸福感 $H_1 + H_2 + … + H_k$。

给定高桥君在观看同一类型的电影 $k$ 次时所获得的幸福感 $H_k$ 和今天的电影时间表，请计算高桥君今天观看电影所获得的总幸福感的最大值。

注意，不允许在电影播放过程中开始观看电影或者停止观看电影。

此外，如果两部电影的播放时间不重叠，即使没有任何空闲时间，也可以观看这两部电影。

输入

输入从标准输入中获取，具有以下格式。

$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$

• 第一行是表示今天上映的电影数量的整数 $N (1≦N≦3000)$。
• 第二行包含 $N$ 个数字。其中第 $i (1≦i≦N)$ 个整数 $H_i(1≦H_i≦10000)$ 表示连续观看电影 $i$ 次时获得的幸福感。
• 对于 $i＜j$，保证 $H_i≦H_j$。
• 从第三行开始，共有 $N$ 行表示今天上映的电影信息。其中第 $i (1≦i≦N)$ 行包含一个整数 $M_i(1≦M_i≦N)$ 表示第 $i$ 部电影的类型，以及用空格分隔的整数 $S_i, E_i(0≦S_i＜E_i≦100000)$ 表示开始时间和结束时间。

输出

输出高桥君今天观看电影所获得的总幸福感的最大值，输出一行。输出末尾包含换行符。

示例1

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

输出示例1

300

如果观看第1部电影和第4部电影，那么就连续看了两次类型为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

来源

Code Formula 2014 本赛