Constellation Erasure

JOI took a photo of an N×N grid. In the grid, the cell in the i-th column and the j-th row is denoted by \((i,j)\). In column \(i\), the bottom \(A_i\) cells (that is, rows \(1,2,\dots,A_i\)) are occupied by small white boats. In addition, there are M stars placed on some cells: the \(i\)-th star is in cell \((X_i,Y_i)\) with a removal cost of \(C_i\) if it is painted over (turned into a black cell). All other cells are simply black (empty).

JOI defines a constellation as any submatrix (i.e. a contiguous rectangular region) that:

1. Contains no white boats.
2. Contains at least two stars.

Since JOI has been studying constellations for 114514 years, he is fed up. He now wants to paint over some stars (with a cost) so that no boat‐free submatrix contains two or more stars. In other words, after painting over some stars, among the remaining stars that lie in boat–free positions the following must hold: for every two remaining stars with coordinates \((x_1,y_1)\) and \((x_2,y_2)\) (with \(x_1 < x_2\)), it must be that

\(\min(y_1,y_2) \leq \max_{i=x_1}^{x_2}A_i\).

Note: A star that lies in a cell where \(y \le A_x\) (i.e. within the boat region) is safe since any boat–free submatrix cannot include that cell. Only stars with \(y>A_x\) (called active stars) may form constellations.

Your task is to choose some active stars to keep (and paint over the others) so that no two kept active stars form a constellation. Painting (removing) the \(i\)-th star costs \(C_i\). Compute the minimum total unnaturalness (i.e. total removal cost) needed so that no boat‐free submatrix contains at least two stars.

Restated mathematically: For every pair of kept active stars with \(x_1

[ \min(y_1,y_2) \le \max_{i=x_1}^{x_2}A_i. ]

Let the total removal cost be the sum of (C_i) for all stars painted over. Minimize that cost.

inputFormat

The input is given in the following format:

N
A1 A2 ... AN
M
X1 Y1 C1
X2 Y2 C2
... 
XM YM CM

All numbers are integers. The boat cells in column \(i\) are rows \(1\) through \(A_i\). Note that a star at \((x,y)\) is active if \(y>A_x\); otherwise it is safe and never forms part of a constellation.

outputFormat

Output a single integer: the minimum total cost required so that there exists no boat–free submatrix containing at least two stars.

sample

3
0 100 0
2
1 101 10
3 101 10

10