记录编号	37453	评测结果	AAAAAAAAAA
题目名称	216.越狱	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.608 s
提交时间	2012-03-30 10:28:16	内存使用	0.42 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

const int oo=~0u>>1;

struct Node
{
	int a,b;
}A[10010];

int N,L,P,f[2][10010],ans=oo;

bool operator <(Node a,Node b)
{
	return a.a>b.a;
}

void dp()
{
	bool fl=false;
	for(int i=1;i<=N;i++)
	{
		fl=!fl;
		memset(f[fl],-1,sizeof(f[fl]));
		for(int j=0;j<=i&&j<ans;j++)
		{
			int tmp=f[!fl][j]-(A[i-1].a-A[i].a);
			if(tmp>=0)
				f[fl][j]=max(f[fl][j],tmp);
			if(j)
			{
				tmp=f[!fl][j-1]-(A[i-1].a-A[i].a);
				if(tmp>=0)
					f[fl][j]=max(f[fl][j],tmp+A[i].b);
			}
			if(f[fl][j]-A[i].a>=0&&f[fl][j]<ans)
				ans=j;
		}
	}
}

int main()
{
	freopen("prisonbreak.in","r",stdin);
	freopen("prisonbreak.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d%d",&A[i].a,&A[i].b);
	scanf("%d%d",&L,&P);
	A[0].a=L;
	sort(A+1,A+1+N);
	for(int i=1,tmp=P-(L-A[1].a);i<=N;i++)
		if(tmp<0)
		{
			printf("-1\n");
			return 0;
		}
		else
		{
			tmp-=A[i].a-A[i+1].a;
			tmp+=A[i].b;
		}
	f[0][0]=P;
	dp();
	printf("%d\n",ans);
	return 0;
}