货物运输

题目描述

在一条长度为 $L$ 的高速公路上，从 $0$ 到 $L$ 的每个位置都建有一个仓库。

现在有 $N$ 件货物运输的订单，第 $i$ 个订单需要将一件货物从位置 $S_i$ 的仓库运送到位置 $T_i$ 的仓库。

运输员小 A 负责本次所有货物的运输。他的车辆从高速公路的起点 $0$ 出发，一次只能运输一件货物，并且可以中途将货物临时放到某个仓库，回头再来取。最终必须停在终点位置 $L$。

为了节省燃油，小 A 希望最小化总行驶距离。

请你计算，在可以任意调整送货顺序的前提下，小 A 最少需要行驶的总距离。

输入格式

输入共 $N + 1$ 行：

• 第一行包含两个整数 $N$ 和 $L$，分别表示货物数量和高速公路的总长度。
• 接下来 $N$ 行，每行两个整数 $S_i$ 和 $T_i$，表示第 $i$ 件货物的起始位置和目的地位置。

输出格式

输出一个整数，表示小 A 最少需要行驶的总距离。

样例输入

3 20
6 12
10 2
19 18

样例输出

38

样例解释

一种最优运输顺序如下：

1. 从位置 0 到 10，准备运输第 2 件货物，行驶距离 10
2. 从 10 到 2，完成第 2 件货物，行驶距离 8
3. 从 2 到 6，准备运输第 1 件货物，行驶距离 4
4. 从 6 到 12，完成第 1 件货物，行驶距离 6
5. 从 12 到 19，准备运输第 3 件货物，行驶距离 7
6. 从 19 到 18，完成第 3 件货物，行驶距离 1
7. 从 18 到终点 20，行驶距离 2

总行驶距离为 $10 + 8 + 4 + 6 + 7 + 1 + 2 = 38$

数据范围与约定

• 对于 40% 的数据，满足 $1 \leq N \leq 1000$
• 对于 100% 的数据，满足 $1 \leq N \leq 10^5$，$1 \leq L \leq 10^9$，$0 \leq S_i, T_i \leq L$