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 $N$ segments of the same length. The segments are numbered from $1$ to $N$ from left to right. In segment $i$ there are $a\_i$ fertilisers and were planted $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 $i$ to segment $j$ costs $|i - j|$.

Find the cheapest way to fertilise all the potatoes.

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

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

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

• $1 ≤ N ≤ 500\\,000$
• $0 ≤ a\_i , b\_i ≤ 1\\,000\\,000$