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

无

无

#### 样例 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}