DMOPC '18 Contest 5 P5 - A Hat Problem

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem types

N people have gathered to trade their hats! They have numbered themselves from 1 to N and lined up in this order. The i^\text{th} person initially has a hat with value v_i but would like a hat with value w_i. 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 N times until everyone has left.

At the end of this process, say person i left wearing a hat valued at h_i. The overall unhappiness is then defined as \sum_{i=1}^N |h_i - w_i|. Can you help these traders minimize their overall unhappiness?


1 \le v_i, w_i \le 1\,000\,000

Subtask 1 [20%]

1 \le N \le 20

Subtask 2 [30%]

1 \le N \le 2\,000

Subtask 3 [50%]

1 \le N \le 200\,000

Input Specification

The first line contains a single integer N.
The next N lines each contain two space-separated integers, v_i and w_i.

Output Specification

Output a single space-separated integer, the minimum possible unhappiness.

Sample Input

15 4
3 18
10 3
8 2

Sample Output


Explanation for Sample

The first person trades his hat with the second person in line and leaves with a hat of value 3. The next three people leave without any more trades. The overall unhappiness is |3-4| + |15-18| + |10-3| + |8-2| = 17 which is the minimum.


There are no comments at the moment.