最长k可重区间集问题

题目描述

给定实直线 $\text{L}$ 上 $n$ 个开区间组成的集合 $\mathbf{I}$,和一个正整数 $k$,试设计一个算法,从开区间集合 $\mathbf{I}$ 中选取出开区间集合 $\mathbf{S}\subseteq\mathbf{I}$,使得在实直线 $\text{L}$ 上的任意一点 $x$,$\text{S}$ 中包含 $x$ 的开区间个数不超过 $k$,且 $\sum_{z\in\text{S}}\lvert z\rvert$ 达到最大($\lvert z\rvert$ 表示开区间 $z$ 的长度)。 这样的集合 $\mathbf{S}$ 称为开区间集合 $\mathbf{I}$ 的最长 $k$ 可重区间集。$\sum_{z\in\text{S}}\lvert z\rvert$ 称为最长 $k$ 可重区间集的长度。 对于给定的开区间集合 $\mathbf{I}$ 和正整数 $k$,计算开区间集合 $\mathbf{I}$ 的最长 $k$ 可重区间集的长度。

输入输出格式

输入格式


输入的第一行有 $2$ 个正整数 $n$ 和 $k$,分别表示开区间的个数和开区间的可重叠数。接下来的 $n$ 行,每行有 $2$ 个整数,表示开区间的左右端点坐标。

输出格式


输出最长 $k$ 可重区间集的长度。

输入输出样例

输入样例 #1

4 2
1 7
6 8
7 10
9 13 

输出样例 #1

15

说明

对于 $100\%$ 的数据,$1\le n\le 500$,$1\le k\le 3$。