Problem Description

Snuke received $ N $ intervals as a birthday present. The $ i $ -th interval is $ [-L_i, R_i] $. It is guaranteed that $ L_i $ and $ R_i $ are positive. In other words, the origin is always inside each interval.

Snuke dislikes overlapping intervals, so he decided to move some of them. For any positive integer $ d $, if he pays $ d $ dollars, he can choose one interval and move it by a distance of $ d $. That is, if the chosen interval is $ [a, b] $, he can make it $ [a+d, b+d] $ or $ [a-d, b-d] $.

Snuke can perform this type of operation any number of times. After all operations, no two intervals should intersect (touching at the boundaries is allowed). Specifically, the length of the intersection of any two intervals must be 0.

Find the minimum cost required to achieve this goal.

Input Format

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

$ N $ $ L_1 $ $ R_1 $ : $ L_N $ $ R_N $

Output Format

Output the minimum cost required to achieve the goal.

Sample Input and Output

Sample Input #1

4
2 7
2 5
4 1
7 5

Sample Output #1

22

Sample Input #2

20
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80
57 18
34 28
76 55
21 80

Sample Output #2

7337

Notes/Hints

Constraints

• $1 \leq N \leq 5000$
• $1 \leq L_i, R_i \leq 10^9$
• All values inputted are integers.

Sample Explanation 1

One optimal way is as follows:
- Move interval $ [-2, 7] $ to $ [6, 15] $ for $ 8 $ dollars
- Move interval $ [-2, 5] $ to $ [-1, 6] $ for $ 1 $ dollar
- Move interval $ [-4, 1] $ to $ [-6, -1] $ for $ 2 $ dollars
- Move interval $ [-7, 5] $ to $ [-18, -6] $ for $ 11 $ dollars
The total cost is $ 8 + 1 + 2 + 11 = 22 $ dollars.

见题面 Input 部分

见题面 Output 部分