给定实直线 \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 个整数，表示开区间的左右端点坐标 l,r，数据保证 l。

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

网络流与线性规划24题