[AdditionalFile2385.zip](file://AdditionalFile2385.zip?type=additional_file)

#2385. 「USACO 2018.01 Platinum」Lifeguards

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2018 January Contest, Platinum Problem 1. Lifeguards

农夫约翰为他的奶牛们开了一个游泳池。简单起见，泳池每天在时刻 $1$ 开门，一直到时刻 $10^9$ 才关闭。
为确保奶牛的安全，他雇佣了 $N$ 只救生牛，分别编号为 $1,2,\ldots,N$。
每只救生牛都有固定的工作时段。救生牛 $i(1\le i\le N)$ 的工作时段可以用两个整数 $s_i, t_i$ 描述，表示救生牛 $i$ 的工作时段为 $(s_i, t_i]$ 。例如，一个救生牛的 $s_i=4, t_i=7$，则它在时刻 $4+1=5$ 开始工作，在时刻 $7$ 结束工作，共覆盖三个时刻（不含起始时刻，含结束时刻）。
现在约翰难以负担救生牛的高额工资，他需要解雇恰好 $K$ 头救生牛。求剩余的救生牛最多能够覆盖多少时刻（某个时刻被覆盖当且仅当这时有至少一个救生牛在工作）。

输入格式

第一行有两个整数 $N,K$，用空格分隔。
在接下来的 $N$ 行中，第 $i$ 行 $1\le i\le N$ 有两个整数 $s_i, t_i$，用空格分隔。
有些救生牛的工作时段可能会相交。

输出格式

输出一个数字，表示剩余的救生牛最多能够覆盖多少时刻。

样例

输入

3 2
1 8
7 15
2 14

输出

12

约翰应该开除救生牛 $1$ 和救生牛 $2$。

数据范围与提示

$1≤K≤N≤10^5, 1≤K≤100$。