当前没有测试数据。

题目描述

小 $A$ 是一个美食爱好者。市里新开了一家美食街，这当然是小 $A$ 不能错过的盛宴啦。

美食街是一条笔直的直线，在街道的不同的点上，有着不同种类的美食，第 $i$ 个美食店的位置为 $x_i$ ，美食品种编号为 $p_i$ 。

这么多种美食让小 $A$ 眼花缭乱，小 $A$ 想要品尝所有品种的美食，又想走最少的路。

请编程帮助小 $A$ 计算，他品尝所有品种的美食，要走的最短路程有多长？

输入

第 $1$ 行有一个整数 $N$ ，表示街道上美食店的总数量；

接下来 $N$ 行，每行有 $2$ 个整数 $x_i$ 和 $p_i$ ，分别代表了不同美食店的位置，以及这个美食店的美食品种。

测试数据保证同一个位置 $x_i$ ，只会开一家美食店。

输出

输出一个整数，代表小 $A$ 要走的最短路程；

路程的计算方式为：如果从 $x_i$ 点到 $x_j$ （ $x_i≤x_j$ ）包含了所有品种的美食，那么路程长度 $=x_j - x_i$ 。

样例

7
2 2 
1 3
5 2
4 1
6 3
10 2
8 1

2

说明

【样例解释】

样例中 $x_i$ 可选取区间 $[4,6]$ ，可以包含所有的美食品种。

【数据范围】

对于 $20\%$ 的数据， $10≤n≤20$ ；

对于另外 $40\%$ 的数据， $10≤n≤1000$ ；

对于 $100\%$ 的数据， $1≤n≤50000$ ， $1≤x_i,p_i≤10^9$ ；