Potatoes and fertilizers

문제

Farmer Gumbauskas is growing potatoes. He planted potatoes in one long furrow and placed bags with fertilisers next to the furrow.

Assume that the furrow consists of $NN$ segments of the same length. The segments are numbered from $11$ to $NN$ from left to right. In segment $ii$ there are $a_{i}a\_i$ fertilisers and were planted $b_{i}b\_i$ potatoes. One fertiliser unit is required to fertilise one planted potato. There is enough fertiliser for all the potatoes, i.e. a_1 + \cdots + a_N ≥ b_1 + \cdots + b_N.

However, it costs to transfer fertiliser from one segment to another. To transfer one unit of fertiliser from segment $ii$ to segment $jj$ costs $\mathrm{\mid }i-j\mathrm{\mid }|i\; -\; j|$.

Find the cheapest way to fertilise all the potatoes.

입력

The length of the furrow $NN$ is given in the first line.

Each of the remaining $NN$ lines contain two integers $a_{i}a\_i$ and $b_{i}b\_i$ – the amount of fertiliser unit and the amount of potatoes planted in segment $ii$. The segments are given in the increasing order of $ii$.

출력

Output the smallest possible cost of fertilising all the planted potatoes.

6
1 2
0 0
2 0
0 0
0 0
0 1

5

7
2 0
2 0
2 0
0 5
2 0
2 0
2 0

6