Lifeguards

提交数: 12, 通过率: 25%, 平均分: 50.83

农夫约翰为他的奶牛们开了一个游泳池，他认为这将有助于他们放松和生产更多的牛奶。为确保安全，他请了N只

牛做救生员，每只牛都有一个工作时间，为一些连续的时间间隔为了简单起见，泳池每天从时间0打开到到10^9，

所以每个区间都可以用两个整数来描述，给定的这两个整数就是区间的开始和结束时刻。例如，一个救生员从t =

4时开始工作和在t=7时结束，共覆盖三个时间单位（注意端点也是覆盖到的时间点）。但不幸的是，农夫约翰雇佣

了比它支付能力多出K个的救生员。他需要开除正好K个救生员，求出剩余的救生员最大能够覆盖多长的时间（一段

时间被覆盖当且仅当这时有至少一个救生员在工作）

第一行包含N和K（K≤N≤10^5，1≤K≤100）

接下来的N行，每行描述一个在区间1...10^9上的救生员

给定这个救生员区间的开始和结束位置，其中有些救生员的区间可能会相交。

请输出一个数字，表示如果农夫约翰开除K个救生员，剩余救生员最大能够覆盖的时间长度

农夫约翰应该开除掉覆盖1...8和7...15两个区间的两个救生员

时间限制: 1000ms
空间限制: 128MB

来源: Usaco2018 Jan Platinum