题目描述

酷 J 最近成了 Jackson 先生，一位生意人，他现在要打很多电话。今天他有 $n$ 个电话要接。每个电话已知预定的开始时刻 $t_i$（自当天 0 点起的秒数）和持续时间 $d_i$（秒数）。所有 $t_i$ 互不相同。Jackson 先生是个大人物，从不主动拨打电话，所有电话都是打进来的。

Jackson 先生不是凯撒，没法一心多用。如果有人在他还没结束上一通电话时打来，他就把新电话放进等待队列。当前电话一结束，他立刻从队列中取出最早打来的那通开始接。如果他从第 $t$ 秒开始接一通电话、通话持续 $d$ 秒，那么他在第 $t, t+1, \ldots, t+d-1$ 秒是忙的，可以在第 $t+d$ 秒接新电话。注意：如果电话打来时他正好空闲，他不能把这通电话挂起等待。

Jackson 先生也不是拿破仑，他喜欢睡觉。所以有时他会放纵一下，无视一通电话，就像它从未被安排过一样。他最多可以无视 $k$ 通电话。注意：他忙着通话时打来的电话也可以被无视。

假设 Jackson 先生可以任选当天（秒数从第 1 秒到第 86400 秒，含两端）的一段连续空闲时间用来睡觉，求他今天最多能睡多少秒？

注意：有些电话可以延续或推迟到第二天甚至更晚。但睡觉的时间段必须完全落在当天之内。

输入格式

输入的第一行包含两个用空格隔开的整数 $n$、$k$（$0 \le k \le n \le 4000$）。接下来 $n$ 行描述今天的电话，每行两个用空格隔开的整数 $t_i$ 和 $d_i$（$1 \le t_i, d_i \le 86400$）。所有 $t_i$ 互不相同，电话按 $t_i$ 严格递增的顺序给出。各电话的占用时段 $[t_i, t_i + d_i - 1]$ 可以任意相交。

输出格式

输出一个 0 到 86400 之间的数——Jackson 先生今天最多可能的睡觉秒数。

3 2
30000 15000
40000 15000
50000 15000

49999

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

39999

说明/提示

第一组样例的最优方案是无视前两通电话。

第二组样例中，无视第三通电话最好。此时 Jackson 先生的通话安排为：第一通从第 1 秒到第 20000 秒；第二通从第 20001 秒到第 30000 秒；第四通从第 30001 秒到第 40000 秒（第三通被无视）；第五通从第 80000 秒到第 139999 秒。于是最长的空闲时段是从第 40001 秒到第 79999 秒。