Problem Description

AtCoder Market is a supermarket represented by a grid of $1,000,000,000$ squares connected in a single row. Here, the $i$-th square from the left is referred to as "square $i$".

One day, $N$ shoppers come to AtCoder Market. The $i$-th shopper will buy items located at square $A_i$ and square $B_i$.

Square1001 decided to install one entrance and one exit in AtCoder Market. Both the entrance and exit can be placed on any square, and they can be at the same location.

Shoppers will move along the following path:

• Start from the entrance, pass through squares $A_i$ and $B_i$, and end at the exit.

When moving between adjacent squares takes $1$ second, find the minimum total travel time for all shoppers when the entrance and exit are optimally placed.

Input Format

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

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : : $ A_N $ $ B_N $

Output Format

Output the minimum total travel time for all shoppers in seconds.

Sample Input and Output

Sample Input #1

3
5 7
2 6
8 10

Sample Output #1

18

Sample Input #2

5
1 71
43 64
13 35
14 54
79 85

Sample Output #2

334

Sample Input #3

11
15004200 341668840
277786703 825590503
85505967 410375631
797368845 930277710
90107929 763195990
104844373 888031128
338351523 715240891
458782074 493862093
189601059 534714600
299073643 971113974
98291394 443377420

Sample Output #3

8494550716

Notes/Hints

Constraints

• $1 \leq N \leq 30$
• $1 \leq A_i < B_i \leq 1,000,000,000$

Subtasks and Points

This problem is divided into several subtasks, and your submission will be considered correct for a subtask if it passes all test cases in that subtask. The score of your source code will be the sum of the points of the correctly solved subtasks.

1. (195 points): $1 \leq A_i < B_i \leq 100$ is satisfied. Also, the squares for the entrance and exit that minimize the travel time are among squares $1, 2, 3, ..., 100$.
2. (105 points): No additional constraints.

Note

Be aware that the answer may not fit within the range of a 32-bit integer type due to the constraints of this problem. For example, in C/C++, you can use the long long type, which is a 64-bit integer type.

Sample Explanation 1

For example, if the entrance is set at square $5$ and the exit at square $7$, each shopper will move as follows:

• Shopper 1: square 5 -> 6 -> 7
• Shopper 2: square 5 -> 4 -> 3 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
• Shopper 3: square 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7

(Bold indicates where the shopper bought items)

Shoppers 1, 2, and 3 spend 2, 8, and 8 seconds respectively, totaling 18 seconds. It is not possible to achieve a shorter total travel time.

Sample Explanation 2

Placing the entrance at square $14$ and the exit at square $64$ can achieve a total travel time of 334 seconds, which is the minimum.

Sample Explanation 3

Placing the entrance at square $189,601,059$ and the exit at square $715,240,891$ can achieve a total travel time of $8,494,550,716$ seconds, which is the minimum.

见题面 Input 部分

见题面 Output 部分