별자리 3

JOI 군은 밤하늘 사진을 찍었다. 사진은 가로와 세로가 각각 $N$ 픽셀인 $N \times N$ 크기이다. 왼쪽에서 $x$번째 열, 아래에서 $y$번째 행에 있는 픽셀을 $(x, y)$라고 한다 ($1 \le x \le N$, $1 \le y \le N$).

사진의 각 픽셀은 건물, 밤하늘, 별 중 하나를 나타낸다. 각각 흰색, 검은색, 노란색이다.

모든 $1 \le i \le N$에 대해, $i$번째 열에서 가장 아래 행부터 아래에서 $A_i$번째 행까지의 픽셀은 건물을 나타내는 흰색 픽셀이다. 별을 나타내는 노란색 픽셀은 $M$개이며, $j$번째 노란색 픽셀은 $(X_j, Y_j)$이다. 나머지 픽셀은 모두 밤하늘을 나타내는 검은색 픽셀이다.

직사각형 영역이 별자리를 보여준다는 것은 다음 두 조건을 모두 만족한다는 뜻이다.

• 영역 안에 흰색 픽셀이 없다.
• 영역 안에 노란색 픽셀이 2개 이상 있다.

JOI 군은 별자리를 보는 데 지쳤다. 노란색 픽셀 일부를 검은색으로 칠해서, 어떤 직사각형 영역도 별자리를 보여주지 않는 사진을 만들려고 한다. 다만 노란색 픽셀을 많이 칠하면 사진이 부자연스러워진다. 정확히는, $j$번째 노란색 픽셀($1 \le j \le M$)을 검은색으로 칠하면 부자연스러움 수준이 $C_j$만큼 증가한다. 처음 부자연스러움 수준은 0이다.

각 노란색 픽셀을 검은색으로 칠했을 때 늘어나는 값이 주어졌을 때, 노란색 픽셀 일부를 칠해서 어떤 직사각형 영역도 별자리를 보여주지 않도록 만든 뒤의 부자연스러움 수준의 최솟값을 구하라.

입력은 다음 형식으로 주어진다.

N
A_1 A_2 \cdots A_N
M
X_1 Y_1 C_1
\vdots
X_M Y_M C_M

모든 값은 정수이다.

노란색 픽셀 일부를 칠해서 어떤 직사각형 영역도 별자리를 보여주지 않도록 만든 뒤, 부자연스러움 수준의 최솟값을 한 줄에 출력한다.

• $1 \le N \le 200\,000$.
• $1 \le A_i \le N$ ($1 \le i \le N$).
• $1 \le M \le 200\,000$.
• $1 \le X_j \le N$ ($1 \le j \le M$).
• $1 \le Y_j \le N$ ($1 \le j \le M$).
• $1 \le C_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• $A_{X_j} < Y_j$ ($1 \le j \le M$).
• $(X_j, Y_j) \ne (X_k, Y_k)$ ($1 \le j < k \le M$).