Fishermen

Time limit1sMemory limit128 MB

Summary

Given fish production along towns on a line with transport losses proportional to distance, find the maximum equal number of children every town can feed via binary search on feasibility.

Level: Hard8 of 10
Topics: Binary search, Greedy, Prefix sum
Solved: No attempts yet

Problem

In a small country, every town lies on one straight road that follows a straight coastline. Except for the first and last towns, each town is directly connected to its two neighboring towns on the road.

The fishermen in each town catch fish every year. Fish caught in a town may be eaten there, or transported along the road to other towns. During transportation, taxes cause 1 ton of fish to be lost for every kilometer traveled.

Every town wants to care for the same number of children. One child eats 1 ton of fish per year. Determine the maximum number of children each town can care for, assuming the fish may be transported cleverly so that all children can be fed.

Input

The first line contains an integer N, the number of towns. 1 <= N <= 100000.

Each of the next N lines contains two integers A and B. A is the position of the town, and B is the amount of fish produced there in one year. 1 <= A <= 1000000000, 0 <= B <= 1000000000.

The towns are given in increasing order of position along the road.

The given data always has a positive answer.

Output

Print one line containing the maximum number of children each town can care for.

Examples3

Example 1
Input
```
3
1 0
2 21
4 0
```
Expected output
```
6
```
Example 2
Input
```
3
5 70
15 100
1200 20
```
Expected output
```
20
```
Example 3
Input
```
4
20 300
40 400
340 700
360 600
```
Expected output
```
415
```