AT_joisc2020_q 治療計画 (Treatment Project)

JOI 村庄有 $N$ 个房屋，编号为 $1$ 到 $N$，每个房屋住有一个村民，第 $i$ 个房屋居住编号为村民 $i$。 现在，这 $N$ 个房屋里的村民全部感染病毒，有 $M$ 个治疗方案被提出，第 $i$ 个治疗方案描述为，在第 $T_i$ 天的晚上，编号在 $[L_i,R_i]$ 区间内的村民被治愈。 病毒还会继续传播，在某天早上，如果村民 $i$ 被感染，那么村民 $i+1$ 和村民 $i-1$ 也会被感染，因为病毒威力巨大，所以被治愈的村民有可能再次被感染。 您是 JOI 国的总理，您要选择一些方案使得 JOI 村庄所有村民全部被治愈，一天可以进行很多方案。 第 $i$ 个方案要花费 $C_i$，求最小花费。

无

无

#### 样例 1 解释 执行过程如下（红色为被病毒感染，绿色为治愈）： 1. 在第二天晚上，执行第 $1$ 个方案，情况如下： $$\color{Red}1\ 2\ 3\ 4\color{Green}\ 5\ 6\ 7\ 8\ 9\ 10$$ 2. 在第三天早上，村民 $5$ 被感染，情况如下： $$\color{Red}1\ 2\ 3\ 4\ 5\color{Green}\ 6\ 7\ 8\ 9\ 10$$ 3. 在第四天早上，村民 $6$ 被感染，情况如下： $$\color{Red}1\ 2\ 3\ 4\ 5\ 6\color{Green}\ 7\ 8\ 9\ 10$$ 4. 在第四天晚上，执行第 $5$ 个方案，情况如下： $$\color{Green}1\ 2\ 3\color{Red}\ 4\ 5\ 6\color{Green}\ 7\ 8\ 9\ 10$$ 5. 第五天早上，村民 $3,7$ 被感染，情况如下： $$\color{Green}1\ 2\color{Red}\ 3\ 4\ 5\ 6\ 7\color{Green}\ 8\ 9\ 10$$ 6. 在第五天晚上，执行第 $3$ 个方案，情况如下： $$\color{Green}1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$$ 全部治愈，这三个方案花费为 $7$，为最小花费。 #### 样例 2 解释 无法使得所有村民全部治愈。 #### 子任务 |子任务|特殊性质|分数| |:-:|:-:|:-:| |$1$|$T_i=1$|$4$| |$2$|$M \le 16$|$5$| |$3$|$M \le 5000$|$30$| |$4$|无|$61$| 对于 $100\%$ 的数据，$1 \le N,T_i,C_i \le 10^9$，$1 \le M \le 10^5$，$1 \le L_i \le R_i \le N$。