题目描述

在一个 n×n 的平面上，在每一行中有一条线段，第 i 行的线段的左端点是(i,Li)，右端点是(i,Ri)。你从 (1,1) 点出发，要求沿途走过所有的线段，最终到达 (n,n) 点，且所走的路程长度要尽量短。 更具体一些说，你在任何时候只能选择向下走一步（行数增加1）、向左走一步（列数减少1）或是向右走一步（列数增加1）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。

输入格式

第 1 行包含一个正整数 n。 第 2 行到第 n+1 行，每行包含两个正整数Li和Ri。

输出格式

仅一行，1个整数，你选择的最短路程的长度。

样例1

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

24

样例2

5
1 3
2 5
3 4
2 4
1 3

20

数据范围

2 ≤ n ≤ 10000； 1 ≤ Li ≤ Ri ≤ n。