JOI-kun 拍摄了一张夜景照片。这张照片由 $N \times N$ 个像素组成，即水平和垂直方向各有 $N$ 个像素。从左侧数第 $x$ 列、从底部数第 $y$ 行的像素（$1 \le x \le N, 1 \le y \le N$）被称为像素 $(x, y)$。

照片中的每个像素显示的是建筑物、夜空或星星，其颜色分别为白色、黑色或黄色。对于每个 $1 \le i \le N$，在第 $i$ 列中，从最底行到从底部数第 $A_i$ 行的像素均为显示建筑物的白色像素。照片中共有 $M$ 个显示星星的黄色像素。第 $j$ 个黄色像素（$1 \le j \le M$）位于像素 $(X_j, Y_j)$。所有其他像素均为显示夜空的黑色像素。

如果照片中的一个矩形区域满足以下两个条件，我们称该区域显示了一个“星座”： 该矩形区域内没有白色像素。 该矩形区域内有两个或两个以上的黄色像素。

JOI-kun 对观察星座感到厌倦了。他想通过将一些黄色像素涂成黑色，使得照片中没有任何矩形区域显示星座。然而，如果他涂掉太多的黄色像素，照片就会变得不自然。更具体地说，如果他将第 $j$ 个黄色像素（$1 \le j \le M$）涂成黑色，照片的不自然程度就会增加 $C_j$。初始时，照片的不自然程度为 0。

请编写一个程序，给定照片的信息以及每个黄色像素涂成黑色后增加的不自然程度，计算在涂掉一些黄色像素使得没有任何矩形区域显示星座的情况下，照片不自然程度的最小值。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N$ $A_1 \dots 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) \neq (X_k, Y_k)$ ($1 \le j < k \le M$)

子任务

1. (14 分) $N \le 300, M \le 300$
2. (21 分) $N \le 2\,000, M \le 2\,000$
3. (65 分) 无附加限制

样例

样例输入 1

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

样例输出 1

2

说明 1

在该样例输入中，左上角顶点为像素 $(1, 5)$、右下角顶点为像素 $(2, 4)$ 的矩形区域显示了一个星座。如果 JOI-kun 将第三个黄色像素涂成黑色，则照片的不自然程度增加 2，且照片中没有任何矩形区域显示星座。由于这是最小值，输出 2。

图 1 展示了该样例输入的照片。

图 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

说明 2

在该样例输入中，最优方案是涂掉第三个和第四个黄色像素。

样例输入 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