题目背景
因为本题数据点过多,另外 3 组数据请在 这里 测试。
JOI 村庄的村民们最近发生了 COVILLAGE-19 疫情!
题目描述
JOI 村庄有 N 个房屋,编号为 1 到 N,每个房屋住有一个村民,第 i 个房屋居住编号为村民 i。
现在,这 N 个房屋里的村民全部感染 COVILLAGE-19 病毒,有 M 个治疗方案被提出,第 i 个治疗方案描述为,在第 Ti 天的晚上,编号在 [Li,Ri] 区间内的村民被治愈。
COVILLAGE-19 病毒还会继续传播,在某天早上,如果村民 i 被感染,那么村民 i+1 和村民 i−1 也会被感染,因为病毒威力巨大,所以被治愈的村民有可能再次被感染。
您是 JOI 国的总理,您要选择一些方案使得 JOI 村庄所有村民全部被治愈,一天可以进行很多方案。
第 i 个方案要花费 Ci,求最小花费。
输入格式
第一行两个整数 N,M 代表村民数和方案数。
接下来 M 行每行四个整数 Ti,Li,Ri,Ci 代表一个治疗方案。
输出格式
一行一个整数代表最小花费。
如果无法全部治愈,输出 −1。
提示
样例 1 解释
执行过程如下(红色为被病毒感染,绿色为治愈):
- 在第二天晚上,执行第 1 个方案,情况如下:
1 2 3 4 5 6 7 8 9 10
- 在第三天早上,村民 5 被感染,情况如下:
1 2 3 4 5 6 7 8 9 10
- 在第四天早上,村民 6 被感染,情况如下:
1 2 3 4 5 6 7 8 9 10
- 在第四天晚上,执行第 5 个方案,情况如下:
1 2 3 4 5 6 7 8 9 10
- 第五天早上,村民 3,7 被感染,情况如下:
1 2 3 4 5 6 7 8 9 10
- 在第五天晚上,执行第 3 个方案,情况如下:
1 2 3 4 5 6 7 8 9 10
全部治愈,这三个方案花费为 7,为最小花费。
样例 2 解释
无法使得所有村民全部治愈。
子任务
子任务 |
特殊性质 |
分数 |
1 |
Ti=1 |
4 |
2 |
M≤16 |
5 |
3 |
M≤5000 |
30 |
4 |
无 |
61 |
对于 100% 的数据,1≤N,Ti,Ci≤109,1≤M≤105,1≤Li≤Ri≤N。
说明
翻译自 第19回日本情報オリンピック 春季トレーニング合宿 Day4 C 治療計画。