记录编号	26910	评测结果	AAAAAAAAAAAA
题目名称	最后的利益	最终得分	100
用户昵称	PurpleShadow	是否通过	通过
代码语言	C++	运行时间	1.276 s
提交时间	2011-07-29 16:00:56	内存使用	0.38 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=10010;
struct range
{
	int a,b;
	range(){}
	range(const int &_a,const int &_b):a(_a),b(_b){}
	bool operator<(const range& t)const
	{return b<t.b||b==t.b&&a<t.a;}
};
range p[N];
int n,s;
void init()
{
	scanf("%d",&n);
	s=0;
	for (int i=1;i<=n;++i)
	{
		scanf("%d%d",&p[i].a,&p[i].b);
		s=max(s,p[i].b);
	}
	sort(p+1,p+n+1);
}
int dp[N];
void slove()
{
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	register int i,j;
	int *x,*y;
	range *t1,*t2;
	for (i=1;i<=n;++i)
	{
		t1=p+i;t2=p;
		x=dp+i;y=dp;
		for (j=0;j<i;++j)
		{
			if (t1->a>=t2->b) *x=min(*x,*y+t1->a-t2->b);
			++t2;++y;
		}
	}
	int Ans=0x3f3f3f3f;
	for (int i=1;i<=n;++i)
		Ans=min(Ans,dp[i]+(s-p[i].b));
	printf("%d\n",s-Ans);
}
int main()
{
freopen("9cwy.in","r",stdin);
freopen("9cwy.out","w",stdout);
	init();
	slove();
	return 0;
}