/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
高橋君と青木君は数直線と区間を使ってゲームをすることにしました。 高橋君は数直線上に立っており、最初は座標 0 にいます。 また、青木君は N 個の区間を持っており、i 個目の区間は [L_i,R_i]、つまり座標が L_i 以上 R_i 以下の点からなる区間となっています。
このゲームは N 回のステップからなります。i ステップ目では以下の手順を踏みます。
- まず青木君は、N 個の区間の内、まだ選んでいない区間を一つ選び、その区間を高橋君に伝える。
- 次に高橋君は、青木君が今回選んだ区間に入るように、数直線上を移動する。
N 回のステップを終えた後、高橋君が座標 0 まで戻ることでゲームは終了します。
高橋君がゲーム全体を通して移動する距離の合計を K としたとき、青木君は K ができるだけ大きくなるように区間を選び、 高橋君は K ができるだけ小さくなるように移動します。 このとき、最終的に高橋君の移動距離の合計 K はいくつになるでしょうか。
制約
- 1 ≦ N ≦ 10^5
- -10^5 ≦ L_i < R_i ≦ 10^5
- L_i と R_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N L_1 R_1 : L_N R_N
出力
高橋君と青木君が上記の条件に従って行動するときの高橋君が動く距離の合計を、1 つの整数値として出力せよ。 ただし、L_i,R_i が整数であるとき、K が整数となることは保証されている。
入力例 1
3 -5 1 3 7 -4 -2
出力例 1
10
高橋君と青木君の行動の一例は以下のようになります。
- 青木君が 1 番目の区間を選び、高橋君は座標 0 から座標 -4 まで距離 4 だけ移動する。
- 青木君が 3 番目の区間を選び、高橋君は座標 -4 のまま動かない
- 青木君が 2 番目の区間を選び、高橋君は座標 -4 から座標 3 まで距離 7 だけ移動する。
- 高橋君は座標 3 から座標 0 まで距離 3 だけ移動する。
このとき高橋君の移動距離の合計は 14 になってしまうので、高橋君の行動は最適ではないですが、 動き方を変えることで、移動距離の合計を 10 にすることができます。
入力例 2
3 1 2 3 4 5 6
出力例 2
12
入力例 3
5 -2 0 -2 0 7 8 9 10 -2 -1
出力例 3
34
Score : 700 points
Problem Statement
Takahashi and Aoki will play a game with a number line and some segments. Takahashi is standing on the number line and he is initially at coordinate 0. Aoki has N segments. The i-th segment is [L_i,R_i], that is, a segment consisting of points with coordinates between L_i and R_i (inclusive).
The game has N steps. The i-th step proceeds as follows:
- First, Aoki chooses a segment that is still not chosen yet from the N segments and tells it to Takahashi.
- Then, Takahashi walks along the number line to some point within the segment chosen by Aoki this time.
After N steps are performed, Takahashi will return to coordinate 0 and the game ends.
Let K be the total distance traveled by Takahashi throughout the game. Aoki will choose segments so that K will be as large as possible, and Takahashi walks along the line so that K will be as small as possible. What will be the value of K in the end?
Constraints
- 1 ≤ N ≤ 10^5
- -10^5 ≤ L_i < R_i ≤ 10^5
- L_i and R_i are integers.
Input
Input is given from Standard Input in the following format:
N L_1 R_1 : L_N R_N
Output
Print the total distance traveled by Takahashi throughout the game when Takahashi and Aoki acts as above. It is guaranteed that K is always an integer when L_i,R_i are integers.
Sample Input 1
3 -5 1 3 7 -4 -2
Sample Output 1
10
One possible sequence of actions of Takahashi and Aoki is as follows:
- Aoki chooses the first segment. Takahashi moves from coordinate 0 to -4, covering a distance of 4.
- Aoki chooses the third segment. Takahashi stays at coordinate -4.
- Aoki chooses the second segment. Takahashi moves from coordinate -4 to 3, covering a distance of 7.
- Takahashi moves from coordinate 3 to 0, covering a distance of 3.
The distance covered by Takahashi here is 14 (because Takahashi didn't move optimally). It turns out that if both players move optimally, the distance covered by Takahashi will be 10.
Sample Input 2
3 1 2 3 4 5 6
Sample Output 2
12
Sample Input 3
5 -2 0 -2 0 7 8 9 10 -2 -1
Sample Output 3
34