题目描述

Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To ensure safety, he hires $N$ cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time $0$ until time $10^9$ on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time $t = 4$ and ending at time $t = 7$ covers three units of time (note that the endpoints are "points" in time).

Unfortunately, Farmer John hired $K$ more lifeguards than he has the funds to support. Given that he must fire exactly $K$ lifeguards, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.

输入格式

The first line of input contains $N$ and $K$ ($K \leq N \leq 100,000, 1 \leq K \leq 100$). Each of the next $N$ lines describes a lifeguard in terms of two integers in the range $0 \ldots 10^9$, giving the starting and ending point of a lifeguard's shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.

输出格式

Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires $K$ lifeguards.

题目大意

题目描述

Farmer John 为他的奶牛们开设了一个游泳池，认为这将帮助它们放松并产更多的奶。

为了确保安全，他雇佣了 $N$ 头奶牛作为救生员，每头奶牛的班次覆盖一天中的某个连续时间段。为简单起见，游泳池每天从时间 $0$ 开放到时间 $10^9$，因此每个班次可以用两个整数描述，分别表示奶牛开始和结束其班次的时间。例如，一头救生员从时间 $t = 4$ 开始到时间 $t = 7$ 结束，覆盖了 $3$ 个单位的时间（注意端点表示时间点）。

不幸的是，Farmer John 多雇佣了 $K$ 名救生员，超出了他的资金支持范围。鉴于他必须解雇恰好 $K$ 名救生员，剩下的救生员的班次能够覆盖的最长时间是多少？如果至少有一名救生员在场，则某个时间段被视为被覆盖。

输入格式

输入的第一行包含 $N$ 和 $K$（$K \leq N \leq 100,000$，$1 \leq K \leq 100$）。接下来的 $N$ 行每行描述一名救生员，用两个范围在 $0 \ldots 10^9$ 的整数表示该救生员班次的开始和结束时间。所有端点都是唯一的。不同救生员的班次可能会重叠。

输出格式

请输出一个数字，表示如果 Farmer John 解雇 $K$ 名救生员后，剩下的救生员的班次能够覆盖的最长时间。

提示

在这个例子中，Farmer John 应该解雇覆盖 $1 \ldots 8$ 和 $7 \ldots 15$ 的救生员。

3 2
1 8
7 15
2 14

12

提示

In this example, FJ should fire the lifeguards covering $1 \ldots 8$ and $7 \ldots 15$.