Problem Description

Takahashi loves watching the same type of movies over and over again. By watching the same type of movies consecutively, he can gain more happiness.

However, Takahashi has a forgetful nature. Once he watches a different type of movie, he completely forgets about the movies he watched before. Even if he watches the same type of movie again, except for the one he watched immediately before, he gains the same amount of happiness as if he were watching that type of movie for the first time.

When Takahashi watches the same type of movie $ k $ times consecutively, he gains $ H_k $ happiness for that session. That means, if he watches the same type of movie consecutively $ k $ times, he will gain a total of $ H_1 + H_2 + ... + H_k $ happiness by the end.

Given the happiness $ H_k $ that Takahashi gains when he watches the same type of movie $ k $ times consecutively, and the schedule of today's movies, find the maximum sum of happiness that Takahashi can gain by watching movies today.

Note that Takahashi cannot start watching a movie in the middle or stop watching a movie in the middle.

Also, if there is no overlap in the broadcast times of two movies, both movies can be watched even if there is no free time in between.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains an integer $N\ (1≦N≦3000)$, representing the number of movies scheduled to be shown today.
• The second line contains $ N $ numbers. The $i\ (1≦i≦N)$th integer $ H_i(1≦H_i≦10000) $ represents the happiness gained when watching the movie $ i $ times consecutively.
• It is guaranteed that $ H_i≦H_j $ when $ i＜j $.
• From the third line, $ N $ lines represent the information of the movies scheduled to be shown today. The $i\ (1≦i≦N)$th line contains an integer $ M_i(1≦M_i≦N) $ representing the type of the $ i $th movie, and integers $S_i,\ E_i(0≦S_i＜E_i≦100000)$ representing the start and end times of the movie, separated by spaces.

Output Format

Output the maximum sum of happiness that Takahashi can gain from watching movies today in one line. Include a newline at the end of the output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

300

Sample Input #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

Sample Output #2

650

Notes/Hints

Sample Explanation 1

By watching the 1st and 4th movies, Takahashi watches type 1 movies consecutively twice, gaining $ 100 + 200 = 300 $ happiness.

见题面 Input 部分

见题面 Output 部分