1769 - 美食街

题目描述

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

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

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

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

输入

1 行有一个整数 N ,表示街道上美食店的总数量;

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

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

输出

输出一个整数,代表小 A 要走的最短路程;

路程的计算方式为:如果从 x_i 点到 x_jx_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≤500001≤x_i,p_i≤10^9

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题