Fishermen

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.

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.

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