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.
3 1 1 3 7 5 4
4
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor