CF158E.Phone Talks

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.

酷仔 J 最近成了一位商人——杰克逊先生，他现在需要打很多电话。今天他共计划了 $ n $ 个电话。对于每个电话，我们知道它预定开始的时刻 $ t_i $（以当天开始后经过的秒数计）及其持续时间 $ d_i $（单位：秒）。所有 $ t_i $ 互不相同。杰克逊先生是一位非常重要的人物，因此他从不主动拨打电话，所有电话均为呼入。

杰克逊先生并非凯撒大帝，无法同时处理多项事务。若某人在他尚未结束上一通电话时呼入，杰克逊先生会将该新来电加入队列并置于等待状态。此时，在当前通话结束后，杰克逊先生会立即从队列中取出最早呼入的电话并开始通话。若杰克逊先生于第 $ t $ 秒开始通话，且该通话持续 $ d $ 秒，则他在第 $ t,,t+1,,\dots,,t+d-1 $ 秒均处于忙线状态，并可在第 $ t+d $ 秒起开始新的通话。注意：若某人呼入时杰克逊先生并未忙线，则他不能将此呼叫置于等待状态。

杰克逊先生也并非拿破仑，他喜欢睡觉。因此，他偶尔会允许自己奢侈地忽略某个电话，就像该电话从未被安排过一样。他最多可忽略 $ k $ 个电话。注意：即使某通电话在他忙线期间呼入，该电话同样可以被忽略。

假设杰克逊先生可从当天（即从第 1 秒至第 86400 秒，含端点）中任选一段连续的时间区间用于睡眠，且该区间内他必须完全空闲（即未处于任何通话中），那么他今天最多能睡多少秒？

注意：部分电话可能被延续或推迟至次日甚至更晚。但所选的睡眠时间段必须完全位于当天之内。

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.

第一行输入包含两个由空格分隔的整数 $n$、$k$（$0 \leq k \leq n \leq 4000$）。接下来的 $n$ 行描述了当天的通话安排。每通电话的描述占一行，由两个由空格分隔的整数 $t_i$ 和 $d_i$（$1 \leq t_i,\,d_i \leq 86400$）组成。所有 $t_i$ 互不相同，且这些通话按 $t_i$ 严格递增的顺序给出。

通话的预定时间区间 $[t_i,\,t_i + d_i - 1]$ 可以任意相交。

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

输出一个从 0 到 86400（含）之间的整数——即杰克逊先生今天最多可能的睡眠秒数。

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.

在第一个样例中，最方便的做法是忽略前两次通话。

在第二个样例中，最佳做法是忽略第三次通话。此时，Jackson 先生的通话时段为：

• 第一次通话：第 1 秒至第 20000 秒，
• 第二次通话：第 20001 秒至第 30000 秒，
• 第四次通话：第 30001 秒至第 40000 秒（第三次通话被忽略），
• 第五次通话：第 80000 秒至第 139999 秒。

因此，最长的空闲时段为第 40001 秒至第 79999 秒。