题目描述

转生成为出租车之后，我绑定了载人升级系统。现在的我，一次性可以搭载四名乘客。

现在系统发布了一项任务：

• 有$n$名乘客想要从各自的出发点到各自的目的地。搭载乘客的顺序只能按照编号顺序依次搭乘（简单的说，如果我之前搭乘过了五号乘客，下一个新上车的乘客只能是六号，再下一个新上车的只能是七号，依次类推），乘客的下车顺序我可以自己决定。只要同一时间车上的乘客数量不超过四名就可以。

这些乘客的出发点和目的地在一条直线上，被依次编号为1到$k$，相邻编号的地点之间可以花费1单位之间通行。注意1和$k$两个地点不相邻。

每次我可以执行下列操作之一：

• 花费1单位时间，移动到相邻编号的地点。例如我在3号地点，可以花费1单位时间移动到2号或者4号地点。
• 当达到编号顺序下的下一个乘客的出发点且乘客没坐满4名时，可以花费1单位时间，让这个乘客上车。
• 当达到车上任何一个乘客的目的地时，可以花费1单位时间，让这个乘客下车。

初始时，系统将我放置在了1号点。所有乘客均已位于各自的出发点等候。系统给我的任务是最优化把所有乘客都送到目标点的时间。送完后不必回到1号点，直接结束任务即可。 为什么转生成为了出租车，还是要做题呢？我的压力一下子上来了。

输入格式

第一行两个数，$n$和$k$，表示共有$n$个人，$k$个地点。

接下来$n$行，其中第$i$行两个正整数$u$和$v$，分别表示编号为$i$的人的出发点和目的地。

输出格式

一个数表示所有乘客均送达时的最小时刻。

2 4
2 3
3 2

7

9 5
1 2
3 2
3 1
3 4
1 2
3 5
3 2
5 1
4 1

30

样例解释

按照如下步骤时间最短：

1. 出租车移动到点2，总时间=1；
2. 第一个人上车，总时间=2；
3. 载第一个人到点3，总时间=3；
4. 第一个人下车，总时间=4；
5. 第二个人上车，总时间=5；
6. 载第二个人到点2，总时间=6；
7. 第二个人下车，总时间=7。

数据规模与约定

对于$30\%$的数据，$1 \le n \le 10$

对于$20\%$的数据，$k = 2$

对于$100\%$的数据，$1 \le n \le 2000, 1 \le k \le 10$

大样例

大样例下载