Problem Description

JOI-kun went to take photos and took a picture of size $N \times N$. The grid at the $i$-th column and $j$-th row is called grid $(i,j)$.

The picture contains white small boats, yellow stars (who knows why stars are yellow), and black empty spaces (who knows what these empty spaces are). In the $i$-th column, up to the $A_i$-th row from the bottom, there are small boats. Additionally, there are $M$ stars, with the $i$-th star located at grid $(X_i, Y_i)$. Apart from the small boats and stars, all other grids are empty spaces.

Now, JOI-kun defines a constellation as a matrix that satisfies the following conditions:

1. It does not contain any small boats.
2. It contains at least $2$ stars.

JOI-kun has been looking at constellations for 114514 years and is tired of them. Therefore, he wants to paint some of the stars black to turn them into empty spaces. Painting the $i$-th star black will increase the unnaturalness of the picture by $C_i$. Find the minimum unnaturalness such that no constellations exist.

Input Format

The first line contains an integer $N$ representing the size of the picture.
The second line contains $N$ integers, where the $i$-th integer $A_i$ represents the position of the small boats.
The third line contains an integer $M$ representing the number of stars.
The next $M$ lines each contain three integers $X_i, Y_i, C_i$ representing a star.

Output Format

Output a single integer representing the minimum unnaturalness such that no constellations exist.

Sample Input and Output

Input Sample #1

5
1 3 4 2 3
3
1 5 3
4 3 2
2 4 2

Output Sample #1

2

Input Sample #2

7
5 6 2 3 6 7 6
5
7 7 5
3 3 7
3 7 10
1 7 6
4 7 8

Output Sample #2

16

Input Sample #3

8
6 8 5 7 3 4 2 1
10
8 2 9
6 6 7
8 3 18
5 8 17
8 5 3
5 5 3
5 4 8
1 8 13
1 7 5
7 4 13

Output Sample #3

44

Notes

Sample 1 Explanation

Painting the third star black is sufficient.

Sample 2 Explanation

Painting the third and fourth stars black is sufficient.

Subtasks

For $100\%$ of the data, $1 \le N, M \le 2 \times 10^5$, $1 \le A_i, X_i, Y_i \le N$, $1 \le C_i \le 10^9$, $A_{X_i} < Y_i$, and no stars are in the same position.

Notes

Translated from The 19th Japanese Olympiad in Informatics Spring Training Camp Day3 A Constellation3.

见题面 Input 部分

见题面 Output 部分