TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

78.6% (77/98)

Submission's AC Ratio

39.5% (119/301)

Tags

Description

在一個沿海的國家中,所有的村莊都是沿著海岸線分佈的(因此它們連成一條直線)。一條筆直的道路連接起所有沿海的村莊。所有的村莊都可以用一個非負整數表示——代表與道路開端的距離(以公里計)。

大部分的居民從事漁業活動。捕魚季節結束以後,在旅遊季節還沒有開始之前,這些居民所捕的魚可以被運送至不同的城鎮。只要某個城鎮的魚貨儲存量至少有 $X$ 噸,那麼該城鎮可以提供 $X$ 位旅客服務。而目標就是盡可能將所有旅客平均的分佈在每個城鎮。換句話說,我們要找出最大的整數 $Y$,使得經過村莊與村莊間的魚貨運送,每一個村莊都至少儲存了 $Y$ 噸以上的魚。

城鎮與城鎮之間可以運輸整數噸數的魚貨。但是每次在運送時,每載送一公里,就會有山上的搶匪搶走一噸的魚。具體來說,若某個村莊欲運送 $F$ 噸的魚到距離 $D$ 公里遠的另一個村莊,那麼實際到達目的地的魚貨量為 $F-D$ 噸。若 $F$ 小於 $D$,那麼整批的魚貨將會消失不見。

當然,你可以任意的在某些村莊將這些魚貨重新包裝、組合,然後再運送出去。舉個例子來說,你可以在城鎮 C,將從城鎮 A 和城鎮 B 運來的魚的各一半,整理一下,然後整批運送到城鎮 D,這樣只算是一次運送。

Input Format

輸入檔可能包含多筆測試資料。

每筆測試資料的第一列包含一個正整數 $N (1 \le N \le 10 ^ 5)$,代表城鎮的數量。

接下來的 $N$ 列,每一列都有兩個整數 $P, F (0 \le P, F \le 10 ^ {12})$,分別代表城鎮的位置以及該城鎮漁民捕到的魚貨量(噸)。城鎮順序已經依照位置的值由小到大排好了。並且所有城鎮的位置都不一樣。

Output Format

對於每筆測試資料請輸出一列包含一個整數:$Y$ 的最大值。

Sample Input 1

3
1 0
2 21
4 0

3
5 70
15 100
1200 20

4
20 300
40 400
340 700
360 600

Sample Output 1

6
20
415

Hints

Problem Source

原TIOJ1406 / 快樂暑假營第四次練習比賽。Problem Setter:Tmt。
(Adapted From IOI2007 Practice Session - FISH)

2023/09/15 Update: 加強測資 by FHVirus
特別感謝 YiaHong 提供 hack.

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 2
2 1000 65536 65536 3
3 1000 65536 65536