JOI-kun 拍了一张夜景照片。这张照片由 $N\times N$ 个像素组成，即长宽均为 $N$ 个像素。从左到右第 $x$ 列，从下往上第 $y$ 行的像素被称为 $(x,y)$。

图片中的每个像素都代表着建筑物、夜空或星星。建筑物颜色是白色、夜空颜色是黑色，星星颜色是黄色。对于 $1\le i\le N$ 的每个 $i$，在第 $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$。

第二行 $N$ 个正整数，第 $i$ 个正整数表示 $A_i$。

第三行一个正整数 $M$。

接下来 $M$ 行，每行三个正整数 $X_i,Y_j,C_j$，表示一个黄色像素。

输出格式

一行一个非负整数表示答案。

样例一

input

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

output

2

explanation

在样例1中，左下角为$(1,4)$，右上角为$(2,5)$的子矩形形成了一个星座。这也是唯一的星座。

如果JOI-kun将第三个黄色像素涂黑，此时不自然度为$2$，同时为所有合法方案的最小值。

下图为样例1的解释：

样例二

input

7
5 6 2 3 6 7 6
5
7 7 5
3 3 7
3 7 10
1 7 6
4 7 8

output

16

explanation

最优解为将第$3,4$个黄色像素涂黑。

样例三

input

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

output

44

数据范围

子任务1($14$分): $N,M\le 300$。

子任务2($21$分): $N,M\le 2000$。

子任务3($65$分): $N,M\le 200000$。

对于所有测试数据，满足$1\le N,M\le 200000,1\le A_i\le N,1\le X_i,Y_i\le N,1\le C_j\le {10}^9$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载