問題文

高橋君は、同じ種類の映画を何度も見るのが大好きです。同じ種類の映画を連続で見る事で、より多くの幸福度を得ることが出来ます。

ですが、高橋君は忘れっぽいので、一度違う種類の映画を見ると、それ以前に見た映画のことを、綺麗さっぱり忘れてしまいます。以前見た種類の映画を見ても、直前に見た種類の映画以外は、初めてその種類の映画を見た時と同じだけの幸福度を得ます。

高橋君は、 $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

Source Name

Code Formula 2014 本戦