Description

JOI 君去拍照，拍了一张大小为 $N \times N$ 的图片，第 $i$ 列第 $j$ 行的格子称为格子 $(i,j)$。

图里有白色的小白船，黄色的星星（天知道为啥星星是黄色的），黑色的空格（天知道这空格是啥），第 $i$ 列自下往上数到第 $A_i$ 行的格子里都是小白船，另外有 $M$ 颗星星，第 $i$ 颗星星在格子 $(X_i,Y_i)$，除了小白船和星星，其他格子都是空格。

现在 JOI 君定义满足下面的一个矩阵为星座：

1. 不包含小白船
2. 至少包含 $2$ 颗星星

JOI 君已经看星座看了 114514 年了，他厌烦了，所以他要把图片中的一些星星涂黑变成黑色空格，涂黑第 $i$ 颗星星会让图片增加 $C_i$ 的不自然度。求不存在星座的最小不自然度。

Input Format

第一行一个整数 $N$ 代表图片的大小。
第二行 $N$ 个整数第 $i$ 个整数 $A_i$ 代表小白船的位置。
第三行一个整数 $M$ 代表星星的个数。
接下来 $M$ 行每行三个整数 $X_i,Y_i,C_i$ 代表一颗星星。

Output Format

一行一个整数代表不存在星座的最小不自然度。

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

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

16

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

44

Hint

样例 1 解释

把第三颗星星涂黑即可。

样例 2 解释

把第三颗和第四颗星星涂黑即可。

子任务

对于 $100\%$ 的数据，$1 \le N,M \le 2 \times 10^5$，$1 \le A_i,X_i,Y_i \le N$，$1 \le C_i \le 10^9$，$A_{X_i}<Y_i$，没有相同位置的星星。

说明

翻译自 第１９回日本情報オリンピック　春季トレーニング合宿 Day3 A 星座3。