VK Cup 2012 Qualification Round 1 ( E Phone Talks)

Phone Talks
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 ti (in seconds since the start of the day) when it is scheduled to start and its duration di (in seconds). All ti 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.

Input

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 ti and di, (1 ≤ ti, di ≤ 86400). All ti are distinct, the calls are given in the order of strict increasing ti.
Scheduled times of calls [ti, ti + di - 1] can arbitrarily intersect.

Output

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

Sample test(s)

input

3 2
30000 15000
40000 15000
50000 15000

output

49999

input

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

output

39999

Note

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.
처음에 이 문제를 봤을 때 욕심인 줄 알았어요. 연속k시간대를 일일이 취소하고 가장 큰 값을 찾으면 결과예요.제출할 때 pretext 9을 넘기지 못하고 동적 기획일 수도 있다는 것을 알아차렸다.근데 머리가 복잡해졌어.할 마음이 없어요.
CF에서 문제를 푸는 것은 편리하다. 경기를 마치면 다른 사람의 코드를 직접 보고 참고할 수 있다.그러나 다른 사람의 코드를 보는 것이기 때문에 독립적으로 사고하는 과정이 많이 부족할 것이다. 그리고 다음에 비슷한 문제가 발생하면 여전히 제한된 시간 안에 해결하기 어려울 것이다.하지만 다른 방법이 떠오르지 않아 다른 사람의 코드를 보지 않고 배우고 싶은 생각을 배울 수 있다.
대신들은 동태적인 계획을 세우려면 많이 생각해야 한다고 말한다.자기가 생각을 너무 적게 한 게 틀림없어.
다음은 다른 사람의 AC를 모방한 코드입니다.

#include<iostream>
#include<windows.h>
using namespace std;
int t[4010],d[4010];
int dp[4010][4010];

int main(){

	int n,k,i,j,res=0;
	cin>>n>>k;
	for(i=1;i<=n;i++)  cin>>t[i]>>d[i];

	for(i=0;i<=k;i++)
	 dp[0][i]=1;

	t[n+1]=86401;  d[n+1]=1;

	for(i=1;i<=n+1;i++)
		for(j=0;j<=k;j++)
		{
			dp[i][j]=max(dp[i-1][j],t[i])+d[i];

			if(t[i]>dp[i-1][j]) res=max(res,t[i]-dp[i-1][j]);
			 
			if(j>=1)
			dp[i][j]=min(dp[i-1][j-1],dp[i][j]);
		}

		

		cout<<res<<endl;
 

	return 0;


}