Tarzan的相似性

Tarzan的相似性

Problem Description

Tarzan 非常烦数轴因为数轴上的题总是难度非常大。不过他非常喜欢线段,因为有关线段的题总是不难,讽刺的是在一个数轴上有 n 个线段, Tarzan 希望自己喜欢的东西和讨厌的东西不在一起,所以他要把这些线段分多次带走,每一次带走一组,最多能带走 k 次。其实就是要把这些线段分成至多 k 组,每次带走一组,问题远没有那么简单, tarzan 还希望每次选择的线段组都很有相似性,我们定义一组线段的相似性是组内线段交集的长度,我们现在想知道最多分成 k 个组带走, Tarzan 最多能得到的相似性之和是多少?

Input format

第一行两个整数 n 和 k。
接下来 n 行每行两个整数 Li; Ri 表示线段的左右端点。

Output format

一行一个整数,表示最多能得到的相似性之和是多少。

Examples

input 1

5 3 
5 10
4 11
6 9
10 30
20 40

output 1

43

input 2

5 3 
5 11
16 22
14 20
10 20
6 10

output 2

18

input 3

7 3 
1 9
2 9
2 10
5 15
3 14
14 18
16 20

output 3

21

Constrains and Notes

对于 20% 的数据满足: n ≤ 8; k ≤ 5
对于 40% 的数据满足: k; n ≤ 12;
对于 70% 的数据满足: n ≤ 100
对于 100% 的数据满足: 1 ≤ k ≤ n ≤ 6000; 1 ≤ Li < Ri ≤ \(10^6\);
时间限制:1s,空间限制:128MB

信息

ID
1396
难度
9
分类
动态规划 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
1
上传者