UOJ Logo Universal Online Judge

UOJ

#512. 【JOISC2020】应对方案

统计

JOI 国共有 $N$ 个房屋,编号为$1$至$N$。房子按从小到大的顺序排列在一条直线上。每个房屋有恰好一名居民,住在房屋$x$的居民被称为居民$x$。

最近新冠疫情爆发,每个居民都染上了新冠病毒。为了解决这个问题,政府提出了$M$个解决方案,第$i$个解决方案会花费$C_i$元,在第$T_i$天晚上治疗所有编号在$[L_i,R_i]$之间的居民。在治疗后每个居民都在当晚治愈。

病毒的传染方式如下:

  • 若居民$x$在第$i$天早上仍然患有新冠病毒,则第$i$天中午,居民$x-1$(若存在)和居民$x+1$若存在也会感染新冠病毒。

你是JOI王国的高官,你现在需要从$M$个治疗方案中选出若干个执行,使得在所有治疗方案执行结束后,全部居民均被治愈。在可以全部治愈的情况下,你希望花费的金额尽量的小。

输入格式

第一行两个数字$N,M$。

接下来$M$行,每行四个正整数$T_i,L_i,R_i,C_i$,表示一个治疗方案。

输出格式

若不存在全部治愈的选择方案,输出$-1$。

否则输出一个整数表示最小花费的金额。

样例一

input

10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1

output

7

explanation

我们采用如下方案:

  • 第二天晚上执行方案$1$,居民$5,6,7,8,9,10$被治愈。
  • 第三天中午居民 $5$ 被感染。
  • 第四天中午居民 $6$ 被感染。
  • 第四天晚上执行方案$5$,居民$1,2,3$被治愈。
  • 第五天中午居民 $3,7$ 被感染。
  • 第五天晚上执行方案$3$,居民$3,4,5,6,7$被治愈。

该方案花费为$7$,可以证明为最小花费。

样例二

input

10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1

output

-1

样例三

input

10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1

output

7

数据范围

子任务1($4$分):$T_i=1$。

子任务2($5$分):$M \le 16$。

子任务3($30$分):$M \le 5000$。

子任务4($61$分):无特殊限制。

对于所有测试数据,满足$1 \le N \le 10^9,1 \le M \le 100000,1 \le T_i,C_i \le 10^9,1 \le L_i \le R_i \le N$。

时间限制:$\texttt{3S}$

空间限制:$\texttt{512MB}$