Problem : 3 - 童話故事

Problem Statistics

Solved Member: 62　　Submission: 331　　User Tried: 70

Statement:

你看過龍使嗎？那是一部愛與熱血的kuso奇幻童話故事，主角弗利茲在經過了一連串神祕的冒險當上了卡恩國國王（據說卡恩國是由上恩公國與下恩公國在卡恩神的征霸下合併的，而那又是另外一段故事了）。雖然當上了國王似乎是很多人的夢想，但弗利茲可不這麼認為，於是他把國事交給奧黛麗雅，自己則整天帶著契約龍去征服......（略）。

嗯，以上是前情提要。

有一次，弗利茲回卡恩國了！但發現最近國家的錢不夠用，而人民卻意外的有錢，奧黛麗雅因為要維持她美好的形象，只好拜託他的老師，弗利茲，幫忙想個辦法。弗利茲非常的不捨得奧黛麗雅，於是在好好地安慰他後，帶著他的龍想了個辦法，用了一張古老的魔法卡，也就是君富卡！

他要求每個城市所擁有的財產要一致，所以每個城市要將他們多的錢，送往錢較少的城市，而運輸的代價是，你運輸多少距離，就要付出多少金幣的費用，若要運輸的距離>=你所攜帶的金幣，你將被洗劫一空！

宅心仁厚的奧黛麗雅開始有點擔心人民會被壓榨的太多，因此要求算出每個城市最多可以有多少金幣，而多的金幣與運費都可以收下。

為了簡化問題，卡恩國的地圖會是放心狀，每個城市都只跟首都連結。你將擁有每個城市所擁有的金幣，與每個城市距離首都的距離。

Ｐ.Ｓ. 請別欺騙奧黛麗雅，否則弗利茲會率領他的龍殲滅你。

Input:Output:

一個測試檔只有一個測資。
第一個數字是n(1 <=n<= 100000)，代表有ｎ個城市。
接下來有ｎ行，每行有兩個數字Di　Mi，分別代表第ｉ個城市與首都的距離，與第ｉ個城市所擁有的金幣數量。

對於每一筆測試資料，請輸出一個數字，代表每個城市最多能擁有多少金幣。

Sample Input:Sample Output:

Sample Input1：
3
1 11
1 6
4 8

Sample Input2：
2
20 50
20 10

Sample Output1：
7

Sample Output2：
10

HINT:

對於 Sample1
我們可以從城市1將3個金幣送到城市2
城市1的金幣有8個
城市2的金幣有7個
城市3的金幣有8個
這時再從城市1與城市3分別送1個金幣到任意城市，由於費用都不足，錢被收光，全部城市的金幣都剩7個了。

佔總分30%的測試資料中，1 <= n <= 200
佔總分60%的測試資料中，1 <= n <= 1000
對於所有的測試資料而言，1 <= n <= 100000, 1 <= Di, Mi <= 2147483647

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10