软件工程

题目信息

时间限制: 1s

空间限制: 512M

输入文件: se.in

输出文件: se.out

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

输入1

输出1

解释1

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

输入2

输出2

解释2

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

样例3

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

数据范围与提示

对于所有的测试点, $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$