AT_agc069_a [AGC069A] Schedule Optimization

高桥君打算举办一个为期 $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)$ 对应的比赛由以下两位选手进行对决，决出胜者和败者： - 当 $i=1$ 时，由选手 $2j-1$ 与选手 $2j$ 对战； - 当 $i\geq 2$ 时，由与 $(i-1,2j-1)$ 对应比赛的胜者和与 $(i-1,2j)$ 对应比赛的胜者对战。 每场比赛只要决定对战的两位选手所需的所有前置比赛都已完成，且这两位选手都在比赛期间内，即可立即进行。特别地，同一位选手在同一天可以参加多场比赛。 与 $(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$ - 输入均为整数 ## 样例解释 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$。 由 ChatGPT 4.1 翻译