#2385. 「USACO 2018.01 Platinum」Lifeguards

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 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