记录编号	18495	评测结果	AAAAAAWAAA
题目名称	越狱	最终得分	90
用户昵称	Oo湼鞶oO	是否通过	未通过
代码语言	C++	运行时间	0.962 s
提交时间	2010-09-15 14:15:25	内存使用	0.45 MiB

#include <fstream>

#define I_F "prisonbreak.in"
#define O_F "prisonbreak.out"
#define MAX 20001

using namespace std;

int n=0;
long s[MAX]={0},d[MAX]={0};
short o[MAX]={0};
long l=0,p=0;

void Input();
void Exchange(int a, int b);
void Qsort(int l, int r);
void Dyna();
void Output();

int main()
{
	Input();
	Qsort(1,n);
	Dyna();
	Output();
	return 0;
}

void Input()
{
	int i;
	ifstream fin(I_F);
	fin>>n;
	for (i=1; i<=n; fin>>s[i]>>o[i++]);
	fin>>l>>p;
	fin.close();
}

void Exchange(int a, int b)
{
	long t=s[a];
	s[a]=s[b];
	s[b]=t;
	t=o[a];
	o[a]=o[b];
	o[b]=t;
}

void Qsort(int l, int r)
{
	long x=s[l+rand()%(r-l+1)];
	int i=l, j=r;
	do
	{
		while (s[i]>x) i++;
		while (s[j]<x) j--;
		if (i<=j)
			Exchange(i++,j--);
	} while (i<j);
	if (i<r)
		Qsort(i,r);
	if (l<j)
		Qsort(l,j);
}

void Dyna()
{
	int i,j;
	for (i=1; i<=n; s[i]=l-s[i++]);
	d[0]=p;
	
	for (i=1; i<=n; i++)
		for (j=i; j>=0; j--)
			if (d[j-1]>=s[i])
				d[j]=max(d[j],d[j-1]+o[i]);
}

void Output()
{
	bool f=true;
	ofstream fout(O_F);
	for (int i=0; i<=n; i++)
		if (d[i]>=l)
		{
			fout<<i<<'\n';
			f=false;
			break;
		}
	if (f)
		fout<<"-1\n";
	fout.close();
}