在数轴上有 $n$ 条线段,第 $i$ 条线段的左右端点为 $[L_i,R_i]$。
现在蜗蜗需要把这 $n$ 条线段恰好分成 $k$ 组,每一组的价值定义为:该组所有线段的交集长度。并且要求每一组的价值都至少为 $1$。
蜗蜗想知道如何分组,使得这 $k$ 组的价值总和最大,输出这个值。
如果无法将 $n$ 条线段恰好分成 $k$ 组,且每一组的价值都至少为 $1$,那么输出 $0$。
输入格式
第一行包含两个整数 $n$, $k$。
接下来 $n$ 行,每行包含两个整数 $L_i, R_i$。
输出格式
输出一行包含一个整数,表示答案。
样例输入 1
4 3
1 2
3 4
5 8
4 5
样例输出 1
7
样例输入 2
4 2
1 2
3 4
5 8
4 5
样例输出 2
0
样例3-9
见附件文件。样例 3-9 分别满足子任务 1-7 的限制。
样例解释
样例 1:
有两种合法的分组方式。
1.分组为:$\{[1,2]\}$,$\{[3,4],[4,5]\}$,$\{[5,8]\}$。价值总和为:$2+1+4=7$。
2.分组为:$\{[1,2]\}$,$\{[3,4]\}$,$\{[5,8],[4,5]\}$。价值总和为:$2+2+1=5$。
所以答案为 $7$。
样例 2:
没有合法的分组方式,所以答案为 $0$。
数据范围
本题采用捆绑测试。
子任务 1(10分):$k=1$。
子任务 2(5分):$k=n$。
子任务 3(10分):$n \leq 15$, $k=2$。
子任务 4(10分):$n \leq 10$, $k \leq 5$。
子任务 5(15分):$n \leq 100$, $k=2$, $L_i \leq R_i \leq 30$。
子任务 6(25分):$n \leq 500$。
子任务 7(25分):无特殊限制。
对于所有数据,保证 $1 \leq k \leq n \leq 5000$, $1 \leq L_i \leq R_i \leq 10^5$。