[JOISC2020] 治療計画
题目背景
因为本题数据点过多,另外 $3$ 组数据请在 [这里](https://www.luogu.com.cn/problem/U127700) 测试。
JOI 村庄的村民们最近发生了 COVILLAGE-19 疫情!
题目描述
JOI 村庄有 $N$ 个房屋,编号为 $1$ 到 $N$,每个房屋住有一个村民,第 $i$ 个房屋居住编号为村民 $i$。
现在,这 $N$ 个房屋里的村民全部感染 COVILLAGE-19 病毒,有 $M$ 个治疗方案被提出,第 $i$ 个治疗方案描述为,在第 $T_i$ 天的晚上,编号在 $[L_i,R_i]$ 区间内的村民被治愈。
COVILLAGE-19 病毒还会继续传播,在某天早上,如果村民 $i$ 被感染,那么村民 $i+1$ 和村民 $i-1$ 也会被感染,因为病毒威力巨大,所以被治愈的村民有可能再次被感染。
您是 JOI 国的总理,您要选择一些方案使得 JOI 村庄所有村民全部被治愈,一天可以进行很多方案。
第 $i$ 个方案要花费 $C_i$,求最小花费。
输入输出格式
输入格式
第一行两个整数 $N,M$ 代表村民数和方案数。
接下来 $M$ 行每行四个整数 $T_i,L_i,R_i,C_i$ 代表一个治疗方案。
输出格式
一行一个整数代表最小花费。
如果无法全部治愈,输出 $-1$。
输入输出样例
输入样例 #1
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
输出样例 #1
7
输入样例 #2
10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1
输出样例 #2
-1
输入样例 #3
10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1
输出样例 #3
7
说明
#### 样例 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$。
#### 说明
翻译自 [第19回日本情報オリンピック 春季トレーニング合宿](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day4 C 治療計画](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day4/capital_city.pdf)。