记录编号	8517	评测结果	ATTTTTTTTA
题目名称	越狱	最终得分	20
用户昵称	zqzas	是否通过	未通过
代码语言	C++	运行时间	8.001 s
提交时间	2008-11-15 07:25:09	内存使用	0.33 MiB

#include <iostream>

#define MAXN 10010
#define INF 999999

using namespace std;

typedef struct{
	int dis;
	int oil;
}Pos;

int n,ans;
Pos pos[MAXN];

int cmp(const void *a,const void *b)
{
	return ((Pos *)a)->dis - ((Pos *)b)->dis;
}

void dfs(int x,int less,int now)
{
	if (x==0)
	{
		if (now<ans)
			ans=now;
		return;
	}
	if (now>ans)
		return;
	//stop at POS x
	if (  (less+pos[x].oil-(pos[x].dis-pos[x-1].dis))  >=0)
		dfs(x-1,less+pos[x].oil-(pos[x].dis-pos[x-1].dis),now+1);
	//no stop
	if (less-(pos[x].dis-pos[x-1].dis)>=0)
		dfs(x-1,less-(pos[x].dis-pos[x-1].dis),now);
}

void run()
{
	ans=INF;
	dfs(n,0,-1);
	if (ans==INF)
		ans=-1;
}

void ini()
{
	int i;
	cin>>n;
	n++;
	for (i=1;i<=n;i++)
	{
		scanf("%d%d",&pos[i].dis,&pos[i].oil);
	}
	qsort(pos,n+1,sizeof(pos[0]),cmp);
}

int main()
{
	freopen("prisonbreak.in","r",stdin);
	freopen("prisonbreak.out","w",stdout);
	ini();
	run();
	printf("%d",ans);
	return 0;
}