/ 
実行時間制限: 1 sec / メモリ制限: 976 MB
配点：300 点
問題文
AtCoder マーケットは、1 \ 000 \ 000 \ 000 個のマスが 1 列につながったマス目で表されるスーパーマーケットである。ここでは、左から i 番目のマスを「マス i」とする。
ある日、N 人の買い物客が AtCoder マーケットに来る。i 人目の買い物客は、マス A_i にある品物とマス B_i にある品物を買う。
square1001 君は、AtCoder マーケットに入口と出口を 1 つずつ設置することにした。
入口と出口はいずれかのマス目に設置する。入口と出口は同じ場所にあってもよい。
そのとき、買い物客は次のような経路で移動する。
- まず、入口からスタートする。マス A_i と B_i を経由して、出口でゴールする。
すべての買い物客について、隣り合ったマス目に進むのに 1 秒かかるとき、最適に入口と出口を設置したときの「すべての買い物客の移動時間の合計」の最小値を求めなさい。
制約
- 1 \leq N \leq 30
- 1 \leq A_i < B_i \leq 1 \ 000 \ 000 \ 000
小課題・得点
この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。
- (195 点)：1 \leq A_i < B_i \leq 100 を満たす。また、移動時間が最小となるような入口と出口のマスは、マス 1, 2, 3, ..., 100 のどれかである。
- (105 点)：追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
N A_1 B_1 A_2 B_2 : : A_N B_N
出力
「すべての買い物客の移動時間の合計」の最小値を、秒単位で出力してください。
注意
この問題の制約上、答えが 32 ビット整数型の範囲に収まらない可能性があることに注意してください。
例えば C / C++ では、long long 型を使うなどで、64 ビット整数型を使用することができます。
入力例 1
3 5 7 2 6 8 10
出力例 1
18
例えば、入口をマス 5、出口をマス 7 に設定すると、それぞれの買い物客は次のように動くことになります：
- 買い物客 1：マス 5 -> 6 -> 7
- 買い物客 2：マス 5 -> 4 -> 3 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
- 買い物客 3：マス 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7
(太字は「ここで品物を買った」ことを表します)
買い物客 1, 2, 3 はそれぞれ 2, 8, 8 秒間移動にかけます。合計は 18 秒です。
また、18 秒より短い合計移動時間にすることはできません。
入力例 2
5 1 71 43 64 13 35 14 54 79 85
出力例 2
334
入口をマス 14 に、出口をマス 64 に設置すると、合計移動時間を 334 秒にすることができ、これが最小です。
入力例 3
11 15004200 341668840 277786703 825590503 85505967 410375631 797368845 930277710 90107929 763195990 104844373 888031128 338351523 715240891 458782074 493862093 189601059 534714600 299073643 971113974 98291394 443377420
出力例 3
8494550716
入口をマス 189 \ 601 \ 059 に、出口をマス 715 \ 240 \ 891 に設置すると、合計移動時間を 8 \ 494 \ 550 \ 716 秒にすることができ、これが最小です。
Max Score：300 Points
Problem Statement
AtCoder Market is a supermarket consist of 1 \ 000 \ 000 \ 000 squares, connected like a straight line from left to right. Let "square i" the i-th leftmost square. In other words, square i and square i+1 is connected for all integer i \ (1 \leq i \leq 999 \ 999 \ 999).
One day, N buyers came to AtCoder Market for shopping. i-th buyer wants to buy two goods: one in square A_i, and the other in square B_i.
The owner of AtCoder Market, square1001, is going to install one entrance and one exit.
Entrance and exit can be installed at any square, and entrance and exit can be placed at the same sqauare.
Then, the i-th buyer will do shopping in the following way:
- Start from the entrance, then visit squares A_i, B_i, and goal at the exit. They will move in the shortest route.
For all buyers, it takes exactly 1 seconds to move to adjacent square.
What is the minimum sum of durations of shoppings, when the owner chooses the place of entrance and exit optimally?
Constraints
- 1 \leq N \leq 30
- 1 \leq A_i < B_i \leq 1 \ 000 \ 000 \ 000
Subtasks / Scoring
This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.
- (195 points)：1 \leq A_i < B_i \leq 100. Also, both entrance and exit will be square either 1, 2, 3, ..., 100, in the optimal solution.
- (105 points)：No additional constraints.
Input
The input will be given from standard input, in the following format.
N A_1 B_1 A_2 B_2 : : A_N B_N
Output
Print the minimal sum of duration of shopping (in second), in one line.
Note
In this constraints, the answer may not be included in the range of 32-bit integer.
To use 64-bit integers, for example in C / C++, we can use long long type, instead of int.
Sample Input 1
3 5 7 2 6 8 10
Sample Output 1
18
Think about installing entrance in square 5, and exit in square 7. Each buyers will move as follows:
- Buyer No.1：Square 5 -> 6 -> 7
- Buyer No.2：Square 5 -> 4 -> 3 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
- Buyer No.3：Square 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7
(Bold character means that the buyer took the goods)
The buyers 1, 2, 3 will use 2, 8, 8 seconds, respectively, so the total shopping time will be 18 seconds.
There's no method for total shopping time to be shorter than 18 seconds.
Sample Input 2
5 1 71 43 64 13 35 14 54 79 85
Sample Output 2
334
When square1001 installs entrance in square 14 and exit in square 64, the total shopping time will be 334 seconds, and it is minimum.
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
When square1001 installs entrance in square 189 \ 601 \ 059 and exit in square 715 \ 240 \ 891, the total shopping time will be 8 \ 494 \ 550 \ 716 seconds, and it is minimum.