A8408 | 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.

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.