← 返回题目

题库练习出租车

← 上一题下一题 →

A2779 | $出租车$

来源USACO / 2013

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

贝茜正在为农场里的其他奶牛提供出租车服务。奶牛沿着长度为 M 的栅栏聚集在不同位置 （1 <= M <= 1,000,000,000）。不幸的是，他们已经厌倦了目前的位置，每个人都希望沿着栅栏去其他地方。贝茜必须在他们的起点接她的每个朋友，并开车送他们到目的地。贝茜的车很小，所以她一次只能用车运送一头牛。奶牛可以瞬间进出汽车。 为了节省汽油，贝茜希望尽量减少她必须开车的量。给定每头奶牛的起始和结束位置（1 <= N <= 100,000），确定 Bessie 必须做的最少驾驶量。贝茜意识到，为了节省最多的汽油，她可能需要偶尔将一头奶牛放在目的地以外的地方。 贝茜从围栏的最左边位置 0 开始，必须在围栏上最右边的位置 M 结束她的旅程。

输入格式

* 第 1 行：N 和 M 之间用空格分隔。 * 第 2..1+N 行：（i+1）第 （i+1） 行包含两个空格 整数、s_i 和 t_i （0 <= s_i， t_i <= M），表示第 i 头奶牛的起始位置和目的地位置。

输出格式

* 第 1 行：单个整数，表示 Bessie 必须执行的驱动总量。请注意，结果可能不适合 32 位整数。

输入输出样例

输入 #1

2 10 
0 9 
6 5

输出 #1

C++ 编辑器

输入

输出