题目描述

农夫约翰请了一位专业摄影师给他的一些奶牛拍照。

约翰拥有多种不同品种的奶牛，他希望照片中包含每个品种的奶牛至少一头。

约翰的N头奶牛沿一条直线站立在不同的位置。

每头奶牛用其所在位置坐标以及其品种编号来描述。

约翰计划为一段连续区间内的奶牛进行拍照，照片的成本等于它的尺寸大小，即照片中位于两端的奶牛的位置坐标之差。

请帮助约翰计算包含每个品种的奶牛至少一头的照片的最低成本。

输入格式

第一行包含整数N。

接下来N行，每行包含两个整数x,ID，表示一头奶牛的坐标位置以及品种编号。

输出格式

输出满足条件的照片的最低成本。

6
25 7
26 1
15 1
22 3
20 1
30 1

4

提示

数据范围

1≤N≤50000,1≤x,ID≤${10}^9$。