people have gathered to trade their hats! They have numbered themselves from to and lined up in this order. The person initially has a hat with value but would like a hat with value . After some discussion, the hat fans decided on the following method of hat trading: The first person in line can either leave with the hat currently on their head, or they may switch hats with the person directly behind them (if there is anyone) and then leave. This process happens times until everyone has left.
At the end of this process, say person left wearing a hat valued at . The overall unhappiness is then defined as . Can you help these traders minimize their overall unhappiness?
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
The first line contains a single integer .
The next lines each contain two space-separated integers, and .
Output a single space-separated integer, the minimum possible unhappiness.
4 15 4 3 18 10 3 8 2
Explanation for Sample
The first person trades his hat with the second person in line and leaves with a hat of value . The next three people leave without any more trades. The overall unhappiness is which is the minimum.