401368: GYM100418 H Equalize

One of the most important responsibilities of an officer in the army is finding a task for soldiers. So, a brave platoon got an important mission: to group logs into equal piles. Logs have already been factored, but, unfortunately, the numbers of logs in the piles were different. The execution of this order should not take less than an hour, that is why the officer gave the next restrictions: in one minute they can take exactly one log and shift it only to a neighboring pile. Help soldiers to determine how many minutes they need to equalize all the piles of logs.

The first line contains the number N. The next N lines contain the pairs of integer numbers K_i, A_i (1 ≤ N, K_i ≤ 10⁵, 0 ≤ A_i ≤ 10⁵). It means that K_i piles in a row have A_i logs. Each of the first K₁ groups have A₁ logs, after that K₂ groups have A₂ logs and so on.

Output the smallest number of minutes the platoon needs to perform the task. Because the answer may be too large, you should output the answer modulo 10⁹ + 7. It's guaranteed that the answer exists always.

3
4 8
3 1
2 5

42