1627_最长k可重区间集

给定实直线 L 上 n 个开区间组成的集合 I ，和一个正整数 k ，试设计一个算法，从开区间集合 I 中选取出开区间集合 S ⊆ I ，使得在实直线 L 的任何一点 x ，S 中包含点 x 的开区间个数不超过 k 。且 ∑_z∈S∣z∣ 达到最大。这样的集合 S 称为开区间集合 I 的最长 k 可重区间集。∑_z∈S∣z∣称为最长 k 可重区间集的长度。

对于给定的开区间集合 I 和正整数 k ，计算开区间集合 I 的最长 k 可重区间集的长度。

文件的第 1 行有 2 个正整数 n 和 k ( 1 ≤ n ≤ 500 , 1 ≤ k ≤ 3 )，分别表示开区间的个数和开区间的可重迭数。

接下来的 n 行，每行有 2 个整数 l_i 和 r_i ，表示开区间的左右端点坐标，注意可能有 l_i > r_i ，此时请将其交换。

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

4 2
1 7
6 8
7 10
9 13

15