酷J最近变成了商人杰克逊先生,他现在要打很多电话。今天他计划了 n 个电话。对于每个呼叫,我们知道计划开始的时刻 ti(自一天开始以来的秒数)及其持续时间 di(以秒为单位)。所有的ti都是不同的。杰克逊先生是一个非常重要的人,所以他从来不亲自给任何人打电话,所有的电话都会打进来。
杰克逊先生不是凯撒,他不能同时做几件事。如果有人在他尚未完成之前的通话时给他打电话,杰克逊先生会将新的呼叫置于队列中。在这种情况下,当前通话结束后,杰克逊先生立即接听队列中最早的来电并开始通话。如果 Jackson 先生在第二个 t 开始呼叫,并且呼叫持续了 d 秒,则 Jackson 先生在 t、t+1、...、t+d-1 秒忙,他可以在第 t+d 秒开始新的呼叫。请注意,如果有人打电话时杰克逊先生不忙于通话,他就无法保留此呼叫。
杰克逊先生也不是拿破仑,他喜欢睡觉。因此,有时他会允许自己忽略一个电话,就好像它从未被安排过一样。他最多可以忽略 k 个呼叫。请注意,在他忙于通话时打来的电话也可以被忽略。
假设杰克逊先生今天不忙于说话时可以选择任意一个连续的时间段(即从第 1 秒到第 86400 秒(含)),那么他今天最多可以睡多少秒?
请注意,某些通话可以继续或推迟到第二天甚至更晚。但是,睡眠间隔应该完全在当天内。
输入
第一个输入行包含一对由空格分隔的整数 n, k (0 ≤ k ≤ n ≤ 4000)。接下来的 n 行包含今天呼叫的描述。每个调用的描述位于单行上,由两个空格分隔的整数 ti 和 di (1 ≤ ti, di ≤ 86400) 组成。所有的 ti 都是不同的,调用是按照 ti 严格递增的顺序给出的。
预定的调用次数[ti, ti + di - 1] 可以任意交叉。
输出
打印 0 到 86400(含)之间的数字 — Jackson 先生今天睡觉的最大可能秒数。
示例
输入 #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
注意
在第一个示例中,最方便的方法是忽略前两个调用。
在第二个示例中,最好忽略第三个调用。在这种情况下,杰克逊先生会说:
- 第一次调用:从第 1 秒到第 20000 秒,
- 第二次调用:从第 20001 秒到第 30000 秒,
- 第四次调用:从第 30001 秒到第 40000 秒(第三次调用被忽略),
- 第五次调用:从第 80000 次到第 139999 次。
因此,最长的空闲时间是从第 40001 秒到第 79999 秒。