Background

In the blue sky and the Milky Way,
there is a small white boat.
There is an osmanthus tree on the boat,
and a white rabbit is playing.
The oars cannot be seen,
and there is no sail on the boat.
It drifts, drifts, drifting toward the western sky,
crossing that Milky Way river,
heading to the Cloud Kingdom.
After passing through that Cloud Kingdom,
where will it go next?
In that faraway place,
it shines with golden light.
The morning star is a lighthouse,
shining so brightly.
The morning star is a lighthouse,
shining so brightly.

If you get Memory Limit Exceeded on this problem, you can try using C++14.

Problem Description

JOI takes a photo and gets an image of size $N \times N$. The cell in column $i$ and row $j$ is called cell $(i,j)$.

In the image, there are white small boats, yellow stars (who knows why stars are yellow), and black empty cells (who knows what these empty cells are). In column $i$, the cells from the bottom up to row $A_i$ are all small boats. In addition, there are $M$ stars: the $i$-th star is at cell $(X_i,Y_i)$. Except for small boats and stars, all other cells are empty.

Now JOI defines a matrix that satisfies the following as a constellation:

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

JOI has been watching constellations for 114514 years, and he is tired of it. So he wants to paint some stars in the image black to turn them into black empty cells. Painting the $i$-th star black increases the unnaturalness of the image by $C_i$. Find the minimum total unnaturalness such that there is no constellation.

Input Format

The first line contains an integer $N$, representing the size of the image.
The second line contains $N$ integers; 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$, describing one star.

Output Format

Output one integer in a single line, representing the minimum total unnaturalness such that there is no constellation.

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

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

16

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

44

Hint

Explanation for Sample 1

It is enough to paint the third star black.

Explanation for Sample 2

It is enough to paint the third and the fourth stars black.

Subtasks

For $100\%$ of the testdata, $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 there are no stars at the same position.

Notes

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

Translated by ChatGPT 5