시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB44262255.000%

문제

JOI-kun took a picture of the night view. The picture consists of N × N pixels, i.e. N pixels along horizontal and vertical directions. The pixel in the x-th column from the left and the y-th row from the bottom (1 ≤ x ≤ N, 1 ≤ y ≤ N) is called the pixel (x, y).

Each pixel of the picture shows building, night sky, or star. Its color is white, black, or yellow, respectively.

For each i with 1 ≤ i ≤ N, in the i-th column, the pixels from the bottommost row to the Ai-th row from the bottom are white pixels showing buildings. There are M yellow pixels showing stars. The j-th yellow pixel (1 ≤ j ≤ M) is the pixel (Xj, Yj). All the other pixels are black pixels showing night sky.

We say a rectangular region in the picture shows a constellation if the following two conditions are satisfied.

  • There is no white pixel in the rectangular region.
  • There are two or more yellow pixels in the rectangular region.

JOI-kun is tired with watching constellations. By painting some yellow pixels into black, he wants to make a picture such that no rectangular region shows a constellation. However, the picture becomes unnatural if he paints many yellow pixels. More precisely, if he paints the j-th yellow pixel (1 ≤ j ≤ M) into black, then the unnatural level of the picture is increased by Cj. Initially the picture has unnatural level 0.

Write a program which, given the information of the picture and the integer for each yellow pixel which describes how much the unnatural level is increased if the pixel is painted into black, calculates the minimum unnatural level of the picture after painting some yellow pixels such that no rectangular region shows a constellation.

입력

Read the following data from the standard input. All the values in the input are integers.

N
A1 · · · AN
M
X1 Y1 C1
.
.
.
XM YM CM

출력

Write one line to the standard output. Output the minimum unnatural level of the picture after painting some yellow pixels such that no rectangular region shows a constellation.

제한

  • 1 ≤ N ≤ 200 000.
  • 1 ≤ Ai ≤ N (1 ≤ i ≤ N).
  • 1 ≤ M ≤ 200 000.
  • 1 ≤ Xj ≤ N (1 ≤ j ≤ M).
  • 1 ≤ Yj ≤ N (1 ≤ j ≤ M).
  • 1 ≤ Cj ≤ 1 000 000 000 (1 ≤ j ≤ M).
  • AXj < Yj (1 ≤ j ≤ M).
  • (Xj, Yj) ≠ (Xk, Yk) (1 ≤ j < k ≤ M).

서브태스크

번호배점제한
114

N ≤ 300, M ≤ 300.

221

N ≤ 2 000, M ≤ 2 000.

365

No additional constraints.

예제 입력 1

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

예제 출력 1

2

In this sample input, the rectangular region whose left-top vertex is the pixel (1, 5) and right-bottom vertex is the pixel (2, 4) shows a constellation. If JOI-kun paints the third yellow pixel into black, then the unnatural level of the picture is increased by 2 and no rectangular region in the picture shows a constellation. Since this is the minimum value, output 2.

Figure 1 is the picture of this sample input.

Figure 1

예제 입력 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

예제 출력 2

16

In this sample input, it is optimal to paint the third yellow pixel and the fourth one.

예제 입력 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

예제 출력 3

44

채점 및 기타 정보

  • 예제는 채점하지 않는다.