[Usaco2007 Demo]Cow Acrobats

时间限制：5s 空间限制：64MB

题目描述

Farmer John's N (1 <= n="" <="50,000)" cows="" (numbered="" 1..n)="" are="" planning="" to="" run="" away="" and="" join="" the="" circus.="" their="" hoofed="" feet="" prevent="" them="" from="" tightrope="" walking="" swinging="" trapeze="" (and="" last="" attempt="" at="" firing="" a="" cow="" out="" of="" cannon="" met="" with="" dismal="" failure).="" thus,="" they="" have="" decided="" practice="" performing="" acrobatic="" stunts.="" aren't="" terribly="" creative="" only="" come="" up="" one="" stunt:="" standing="" on="" top="" each="" other="" form="" vertical="" stack="" some="" height.="" trying="" figure="" order="" in="" which="" should="" arrange="" themselves="" within="" this="" stack.="" has="" an="" associated="" weight="" (1="" strength="" risk="" collapsing="" is="" equal="" combined="" all="" her="" (not="" including="" own="" weight,="" course)="" minus="" (so="" that="" stronger="" lower="" risk).="" your="" task="" determine="" ordering="" minimizes="" greatest="" collapse="" for="" any="" cows.="" 有三个头牛，下面三行二个数分别代表其体重及力量="" 它们玩叠罗汉的游戏，每个牛的危险值等于它上面的牛的体重总和减去它的力量值，因为它要扛起上面所有的牛嘛.="" 求所有方案中危险值最大的最小="" p="">

输入格式

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

输出格式

* Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk.

样例输入

样例输出

2

OUTPUT DETAILS:

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.

提示

没有写明提示

题目来源

Silver