You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你是一个软件工程师（Software Engineer），是写后端的。有一天你们组的前端程序员的对象问你们组的前端程序员一个问题，前端程序员不会，于是把这个问题丢给了曾经学OI的你：

有一条数轴，上面有 $n$ 条线段，第 $i$ 条为 $[l_i; r_i]$。现在他想把这 $n$ 条线段划分为不超过 $k$ 个集合，每条线段必须恰好属于其中一个集合。定义一个集合的权值为集合里所有线段的交的长度，定义一种划分方案的权值为所有集合的权值之和。求所有满足条件的划分方案中最大的权值。

虽然这和软件工程关系不大，不过热心的你一定可以帮助到同事的对象的。

输入格式

第一行两个正整数 $n,k$。

接下来 $n$ 行，每行两个正整数 $l_i, r_i$，表示一条线段。

输出格式

输出一行一个整数表示最大的权值。

4 3
1 7
9 20
5 15
4 10

24

解释1

分成$\{[1,7], [4,10]\},\{[9, 20]\} ,\{[5, 15]\}$ ， 权值为$3+11+10=24$。

5 3
15 16
9 14
14 20
4 9
8 14

12

解释2

分成$\{[15,16], [9,14], [4,9]\},\{[14, 20]\} ,\{[8, 14]\}$ ， 权值为$0+6+6=12$。

样例3

见附加文件 c3.in 与 c3.out 。此样例满足$n \le 500$。
c3.in
c3.out

数据范围与提示

对于所有的测试点, $1 \le k\le n \le 5000$, $1 \le l_i < r_i \le 10^6$。

• 对于前 $15 \%$ 的数据, 满足 $n \le 12$
• 对于前 $40\%$ 的数据, 满足 $n \le 500$
• 另有 $15 \%$ 的数据, 满足 $n \le 5000, k=2$
• 对于 $100 \%$ 的数据, 满足 $n \le 5000$