Equal Division

There are N teams in a software company. The ith team has Bi employees in it and a total budget of Ai units of money. Each team has to divide their budget within their employees equally. But for some teams, it's not possible to divide the budget equally.

Therefore, the company have to perform revisions in the teams' budget sizes.

In one revision, to revise the budget of ith team, the budget of the first i teams has to be increased by 1.

Your task is to find the minimum number of revisions needed so that for each team, equal distribution of their budget among the employees is possible.

Constraints:

• 1N10^5
• 0A_i10^9
• 1B_i10^9

Input Format:

The first line contains an integer N, denoting the number of teams.

Next N lines contain two space-separated integers, A_i and B_i, each.

Output Format:

In a single line, print the minimum number of revisions needed so that for each team, equal distribution of their budget among the employees is possible.

SAMPLE INPUT

3 1 1 3 7 5 4 

SAMPLE OUTPUT

4 

Explanation

Initially, the budges of the teams are 1, 3 and 5.

In the first revision, the company will increase the budget for first 2 teams by 1. This will make the budgets as 2, 4 and 5.

In next 3 revisions, the company will increase the budget of first 3 teams by 1.

The final budgets will be 5, 7 and 8 which can now be equally distributed within each team.

You cannot achieve the equal distribution characteristic in less than four revisions.