Phone Talks

题意翻译

### 题目描述 cool J最近成了一个商人杰克逊先生，他现在不得不打很多电话。今天他有N个电话计划。对于每个呼叫，我们知道计划开始的时刻Ti（从一天开始的秒数）及其持续时间Di（秒数）。所有Ti都不同。杰克逊先生是一个非常重要的人，所以他从不亲自给任何人打电话，所有的电话都会接通。 杰克逊先生不是凯撒，他不能同时做几件事。如果有人在他还没有结束之前的谈话时打电话给他，杰克逊先生会把新的电话挂在队列中。在这种情况下，在当前通话结束后，杰克逊先生立即从队列中接听最早的来电并开始通话。如果杰克逊先生在第二个T开始通话，通话持续d秒，那么杰克逊先生在第二个T、T+1、…、T+D-1 T、T+1、…、T+D-1是没有时间的，他可以在第二个T+D T+D开始新的通话。注意，如果有人打电话时杰克逊先生没有忙着说话，他就不能把这个电话挂断。 杰克逊先生也不是拿破仑，他喜欢睡觉。所以有时候他会让自己有一种奢侈，无视一个电话，就好像从来没有预定过一样。他最多可以忽略k个电话。请注意，当他正忙着说话时，一个电话也会被忽略。 假设杰克逊先生可以在不忙的时候选择一个任意的连续时间段（也就是说，从第一个到第86400个时间段，包括第86400个时间段），那么他今天能睡的最长时间是多少秒？ 请注意，有些电话可以继续或推迟到第二天甚至更晚。但是，睡眠的时间间隔应该完全在当天之内。 ### 输入输出格式 输入格式： 第一个输入行包含一对由空格分隔的整数n,k（0<=k<=n<=4000 0<=k<=n<=4000）。以下n行包含今天的呼叫说明。每个调用的描述位于单行上，由两个空格分隔的整数Ti，Di( 1<=Ti,Di<=86400)组成。所有的Ti是不同的，调用的顺序是严格递增的Ti。 预定的通话时间[Ti，Ti+Di-1]可以任意交叉。 输出格式： 输出一个从0到86400的数字——杰克逊先生今天睡觉的最大可能秒数。 ### 说明 在第一个示例中，最方便的方法是忽略前两个调用。 在第二个示例中，最好忽略第三个调用。在这种情况下，杰克逊先生会说： 第一次呼叫：从1秒到20000秒， 第二次呼叫：从20001到30000秒， 第四次调用：从第30001秒到第40000秒（忽略第三次调用）。 第五次呼叫：从80000到139999秒。 因此，最长的空闲时间是从40001秒到79999秒。

题目描述

Cool J has recently become a businessman Mr. Jackson, and he has to make a lot of phone calls now. Today he has $ n $ calls planned. For each call we know the moment $ t_{i} $ (in seconds since the start of the day) when it is scheduled to start and its duration $ d_{i} $ (in seconds). All $ t_{i} $ are different. Mr. Jackson is a very important person, so he never dials anybody himself, all calls will be incoming. Mr. Jackson isn't Caesar and he can't do several things at once. If somebody calls him while he hasn't finished the previous conversation, Mr. Jackson puts the new call on hold in the queue. In this case immediately after the end of the current call Mr. Jackson takes the earliest incoming call from the queue and starts the conversation. If Mr. Jackson started the call at the second $ t $ , and the call continues for $ d $ seconds, then Mr. Jackson is busy at seconds $ t,t+1,...,t+d-1 $ , and he can start a new call at second $ t+d $ . Note that if Mr. Jackson is not busy talking when somebody calls, he can't put this call on hold. Mr. Jackson isn't Napoleon either, he likes to sleep. So sometimes he allows himself the luxury of ignoring a call, as if it never was scheduled. He can ignore at most $ k $ calls. Note that a call which comes while he is busy talking can be ignored as well. What is the maximum number of seconds Mr. Jackson can sleep today, assuming that he can choose an arbitrary continuous time segment from the current day (that is, with seconds from the 1-st to the 86400-th, inclusive) when he is not busy talking? Note that some calls can be continued or postponed to the next day or even later. However, the interval for sleep should be completely within the current day.

输入输出格式

输入格式

The first input line contains a pair of integers $ n $ , $ k $ ( $ 0<=k<=n<=4000 $ ) separated by a space. Following $ n $ lines contain the description of calls for today. The description of each call is located on the single line and consists of two space-separated integers $ t_{i} $ and $ d_{i} $ , ( $ 1<=t_{i},d_{i}<=86400 $ ). All $ t_{i} $ are distinct, the calls are given in the order of strict increasing $ t_{i} $ . Scheduled times of calls \[ $ t_{i} $ , $ t_{i}+d_{i}-1 $ \] can arbitrarily intersect.

输出格式

Print a number from 0 to 86400, inclusive — the maximally possible number of seconds for Mr. Jackson to sleep today.

输入输出样例

输入样例 #1

3 2
30000 15000
40000 15000
50000 15000

输出样例 #1

49999

输入样例 #2

5 1
1 20000
10000 10000
20000 20000
25000 10000
80000 60000

输出样例 #2

39999

说明

In the first sample the most convenient way is to ignore the first two calls. In the second sample it is best to ignore the third call. In this case Mr. Jackson will have been speaking: - first call: from 1-st to 20000-th second, - second call: from 20001-st to 30000-th second, - fourth call: from 30001-st to 40000-th second (the third call is ignored), - fifth call: from 80000-th to 139999-th second. Thus, the longest period of free time is from the 40001-th to the 79999-th second.