题目描述

在一个 $n \times n$ 的网格平面上,第 $i$ 行放置了一条水平线段,其左端点坐标为 $(i, L_i)$,右端点坐标为 $(i, R_i)$。

你需要从 $(1,1)$ 出发,沿途走过所有行的线段,最终到达 $(n,n)$,使得总路程最短。

移动规则：你只能向右走一步（列数增加 $1$）、向左走一步（列数减少 $1$）或向下走一步（行数增加 $1$）。当你从第 $i$ 行向下走到第 $i+1$ 行时,必须保证第 $i$ 行的线段已经全部走完。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行,第 $i$ 行两个整数 $L_i$ 和 $R_i$,表示第 $i$ 行线段的左右端点。

输出格式

一个整数,表示最短总路程。

样例

6
2 6
3 4
1 3
1 2
3 6
4 5

24

提示

对于 $100\%$ 的数据, $1 \le n \le 2 \times 10^4$, $1 \le L_i \le R_i \le n$。