There are $$N$$ teams in a software company. The $$i^{th}$$ team has $$B_i$$ employees in it and a total budget of $$A_i$$ 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 $$i^{th}$$ 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:

• $$1 \le N \le 10^5$$
• $$0 \le A_i \le 10^9$$
• $$1 \le B_i \le 10^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.