AT_agc069_a [AGC069A] Schedule Optimization

[problemUrl]: https://atcoder.jp/contests/agc069/tasks/agc069_a 高橋君は全 $ 10^9 $ 日間からなるトーナメント形式の大会を開くことにしました。 選手は $ 2^N $ 人いて、それぞれ選手 $ 1 $、$ \ldots $、選手 $ 2^N $ と呼ばれます。 選手 $ i $ は大会の $ l_i $ 日目から $ r_i $ 日目までの $ r_i-l_i+1 $ 日間参加する予定です。 まず、大会の流れを述べます。$ 1\ \leq\ i\ \leq\ N,\ 1\ \leq\ j\ \leq\ 2^{N-i} $ を満たす整数組 $ (i,j) $ は $ 2^N-1 $ 通りありますが、それらと大会中の試合が一対一で対応します。$ (i,j) $ に対応する試合では以下に述べる $ 2 $ 人の選手が対戦して勝者と敗者を決めます。 - $ i=1 $ の場合、選手 $ 2j-1 $ と選手 $ 2j $ - $ i\ \geq\ 2 $ の場合、$ (i-1,\ 2j-1) $ に対応する試合の勝者と $ (i-1,2j) $ に対応する試合の勝者 各試合は、対戦することになる $ 2 $ 人を決める為に必要な試合すべてが完了していて、かつその $ 2 $ 人が大会に参加中ならばただちに完了させられます。特に、一人の選手が同日に複数の試合を行うことも可能です。 $ (N,\ 1) $ に対応する試合は決勝戦と呼ばれ、これを完了させるのが大会の目的です。 高橋君は決勝戦を完了させて大会を成功させるために、以下の工作を行うことにしました。 - 審判に指示を出し、各試合の勝者を都合よく決める。 - 各選手にお金を払い、参加する日程を変えてもらう。選手 $ i $ に $ l'_i $ 日目から $ r'_i $ 日目まで参加してもらう場合、$ |l_i-l'_i|+|r_i-r'_i| $ 円を支払う必要がある。ここで、$ l'_i,\ r'_i $ は $ 1\leq\ l'_i\ \leq\ r'_i\ \leq\ 10^9 $ を満たす整数である。 高橋君が選手たちに支払う必要のある金額の総和の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ l_1 $ $ r_1 $ $ \vdots $ $ l_{2^N} $ $ r_{2^N} $

支払う必要のある金額の総和の最小値を $ X $ 円とする。$ X $ を出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 18 $ - $ 1\ \leq\ l_i\ \leq\ r_i\ \leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 1 選手 $ 4 $ に $ 1 $ 円を払って $ (l'_4,\ r'_4)=(2,3) $ に変え、他の選手の日程は変えないことにします。すると、例えば以下のようにして決勝戦を完了させることができます。 1. $ 1 $ 日目に $ (1,1) $ に対応する試合(選手 $ 1 $ 対選手 $ 2 $ )を行い、選手 $ 2 $ を勝たせる。 2. $ 3 $ 日目に $ (1,2) $ に対応する試合(選手 $ 3 $ 対選手 $ 4 $ )を行い、選手 $ 3 $ を勝たせる。 3. $ 3 $ 日目に $ (2,1) $ に対応する試合(選手 $ 2 $ 対選手 $ 3 $ )を行い、選手 $ 3 $ を勝たせる。 4. $ 3 $ 日目に $ (1,4) $ に対応する試合(選手 $ 7 $ 対選手 $ 8 $ )を行い、選手 $ 8 $ を勝たせる。 5. $ 4 $ 日目に $ (1,3) $ に対応する試合(選手 $ 5 $ 対選手 $ 6 $ )を行い、選手 $ 5 $ を勝たせる。 6. $ 4 $ 日目に $ (2,2) $ に対応する試合(選手 $ 5 $ 対選手 $ 8 $ )を行い、選手 $ 8 $ を勝たせる。 7. $ 4 $ 日目に $ (3,1) $ に対応する試合(選手 $ 3 $ 対選手 $ 8 $ )を行い、選手 $ 8 $ を勝たせる。 一方、$ 1 $ 円未満の支払いで決勝戦を完了させることはできません。そのため、$ 1 $ が期待される出力です。