Problem Description

Wolves and foxes are scheduled to undergo health checkups. The health checkups will take place over $ N $ days, and each wolf and fox is scheduled to attend on exactly one of these days. On the $ i $th day, there are $ w_i $ wolves and $ f_i $ foxes who wish to attend the health checkup.

However, on each of the $ N $ days, only one type of animal (either wolves or foxes) can be checked. If the preferences conflict, the wolves or foxes who wish to attend on the $ i $th day may have to attend on another day $ j $, resulting in a dissatisfaction score of $ |i-j| $. If there is no available day for a health checkup, the dissatisfaction score is $ 10^{100} $. Each wolf and fox will attend the health checkup on the day that minimizes their dissatisfaction score.

Determine the minimum total dissatisfaction score for all wolves and foxes when deciding optimally which animals to check on each day.

Input Format

The input is given from the standard input in the following format:

$ N $ $ w_1 $ $ f_1 $ : $ w_N $ $ f_N $

Output Format

Output the minimum total dissatisfaction score for all wolves and foxes.

Sample Input and Output

Sample Input #1

6
1 5
1 3
3 4
3 2
5 1
6 2

Sample Output #1

15

Sample Input #2

10
26 37
1 49
1 74
2 99
2 100
2 75
3 62
3 62
2 37
2 37

Sample Output #2

108

Notes/Hints

Constraints

• $2\ \leq\ N\ \leq\ 3000$
• $0\ \leq\ w_i,\ f_i\ \leq\ 10^9$

Sample Explanation 1

It is optimal to check wolves on days $ 3, 5, 6 $ and foxes on days $ 1, 2, 4 $.

见题面 Input 部分

见题面 Output 部分