The cows aren't terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves ithin this stack.

Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows.

* Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.

Put the cow with weight 10 on the bottom. She will carry the other two cows, so the risk of her collapsing is 2+3-3=2. The other cows have lower risk of collapsing.

当i在j的上方时有

- Di=∑−Si

①
- Dj=∑+Wi−Sj

②
当j在i的上方时有

- Di=∑+Wj−Si

③
- Dj=∑−Sj

④
显然我们可以得到
③>①,②>④,②>③

这里面②最大，所以如果我们让i在j的上方最终答案一定不会更优，即证得此贪心策略的正确性。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

struct cow{

	int w,p,sum;

};

int cmp(cow c1,cow c2)

{

	return c1.sum<c2.sum;

}

cow c[50100];

int main()

{

	int n;

	//int w[10100],p[10100];

	//memset(w,0,sizeof(w));

	//memset(p,0,sizeof(p));

	while(~scanf("%d",&n))

	{

		for(int i=0;i<n;i++)

		{

			scanf("%d%d",&c[i].w,&c[i].p);

			c[i].sum=c[i].p+c[i].w;

		}

		//int sum[10100];

		sort(c,c+n,cmp);

		int ans=-0x3f3f3f3f;

		int sum=0;

		for(int i=0;i<n;i++)

		{

			//ans+=c[i].p-c[i-1].w;

			ans=max(ans,sum-c[i].p);

			sum+=c[i].w;

		}

		printf("%d\n",ans);

	}

	return 0;

}