1376: 「网络流 24 题」最长 k 可重区间集
[Creator : ]
Description
给定实直线 L 上 n 个开区间组成的集合 I，和一个正整数 k。
试设计一个算法，从开区间集合 I 中选取出开区间集合 $S \subseteq I$，使得在实直线 L 的任何一点 x，S 中包含点 x 的开区间个数不超过 k。且 $\sum\limits_{z \in S}$ 达到最大。这样的集合 S 称为开区间集合 I 的最长 k 可重区间集。$\sum\limits_{z \in S}$ 称为最长 k 可重区间集的长度。
对于给定的开区间集合 I 和正整数 k，计算开区间集合 I 的最长 k 可重区间集的长度。
试设计一个算法，从开区间集合 I 中选取出开区间集合 $S \subseteq I$，使得在实直线 L 的任何一点 x，S 中包含点 x 的开区间个数不超过 k。且 $\sum\limits_{z \in S}$ 达到最大。这样的集合 S 称为开区间集合 I 的最长 k 可重区间集。$\sum\limits_{z \in S}$ 称为最长 k 可重区间集的长度。
对于给定的开区间集合 I 和正整数 k，计算开区间集合 I 的最长 k 可重区间集的长度。
Input
文件的第 1 行有 2 个正整数 n 和 k，分别表示开区间的个数和开区间的可重迭数。
接下来的 n 行，每行有 2 个整数 $l_i$ 和 $r_i$，表示开区间的左右端点坐标，注意可能有 $l_i > r_i$，此时请将其交换。
接下来的 n 行，每行有 2 个整数 $l_i$ 和 $r_i$，表示开区间的左右端点坐标，注意可能有 $l_i > r_i$，此时请将其交换。
Output
输出最长 k 可重区间集的长度。
Constraints
$1 \leq n \leq 500, 1 \leq k \leq 3$
Sample 1 Input
4 2
1 7
6 8
7 10
9 13
Sample 1 Output
15