[JOISC2020] 星座 3

> 蓝蓝的天空银河里 有只小白船 船上有棵桂花树 白兔在游玩 桨儿桨儿看不见 船上也没帆 飘呀飘呀飘向西天 渡过那条银河水 走向云彩国 走过那个云彩国 再向哪儿去 在那遥远的地方 闪着金光 晨星是灯塔 照呀照得亮 晨星是灯塔 照呀照得亮 **本题被卡空间的可以尝试使用 C++14 通过**

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$ 的不自然度。求不存在星座的最小不自然度。

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

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

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

#### 样例 1 解释 把第三颗星星涂黑即可。 #### 样例 2 解释 把第三颗和第四颗星星涂黑即可。 #### 子任务 |子任务|特殊性质|分数| |:-:|:-:|:-:| |$1$|$N,M \le 300$|$14$| |$2$|$N,M \le 2000$|$21$| |$3$|无|$65$| 对于 $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$，没有相同位置的星星。 #### 说明 翻译自 [第１９回日本情報オリンピック　春季トレーニング合宿](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day3 A 星座3](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day3/constellation3.pdf)。