Problem1147--#6014. 「网络流 24 题」最长 k 可重区间集

1147: #6014. 「网络流 24 题」最长 k 可重区间集

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

输入格式

文件的第 1 1 1 行有 2 2 2 个正整数 n n nk k k,分别表示开区间的个数和开区间的可重迭数。
接下来的 n n n 行,每行有 2 2 2 个整数 li l_i liri r_i ri,表示开区间的左右端点坐标,注意可能有 li>ri l_i > r_i li>ri,此时请将其交换

输出格式

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

样例

样例输入

4 2
1 7
6 8
7 10
9 13

样例输出

15

数据范围与提示

1≤n≤500,1≤k≤3 1 \leq n \leq 500, 1 \leq k \leq 3 1n500,1k3

Source/Category