记录编号	27263	评测结果	AAAAAAAAAAAA
题目名称	最后的利益	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	1.332 s
提交时间	2011-09-04 14:48:21	内存使用	0.46 MiB

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

using namespace std;

long a[10001][5],n,m,ans;

void sort1(long x,long y)
{
	long i,j,k;
	i=x;
	j=y;
	k=a[(x+y)/2][2];
	while(i<=j)
	{
		while(a[i][2]<k)
			i++;
		while(a[j][2]>k)
			j--;
		if(i<=j)
		{
			swap(a[i][2],a[j][2]);
			swap(a[i][1],a[j][1]);
			i++;
			j--;
		}
	}
	if(x<j)
		sort1(x,j);
	if(i<y)
		sort1(i,y);
}

int main()
{
	int i,j;
	freopen("9cwy.in","r",stdin);
	freopen("9cwy.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&a[i][1],&a[i][2]);
	sort1(1,n);
	for(i=1;i<=n;i++)
	{
		a[i][3]=a[i][2]-a[i][1];
		a[i][4]=0;
	}
	a[n][4]=a[n][3];
	for(i=n-1;i>=1;i--)
	{
		for(j=i;j<=n;j++)
			if(a[i][2]<=a[j][1])
				if(a[j][4]+a[i][3]>a[i][4])
					a[i][4]=a[j][4]+a[i][3];
		if(a[i][4]==0)
			a[i][4]=a[i][3];
	}
	ans=0;
	for(i=1;i<=n;i++)
		if(a[i][4]>ans)
			ans=a[i][4];
	printf("%d",ans);
	return 0;
}