题目描述

你受雇为一家酒店建造电梯系统！

酒店有 $k$ 部电梯，初始时你可以选择它们分别停在哪一层。一天当中会有 $n$ 个请求，每个请求由一对 $(l, r)$ 描述，表示有人在第 $l$ 层并希望前往第 $r$ 层。

人们不喜欢久等，因此我们要求请求必须依次完成。更确切地说，第 $i$ 个请求必须在第 $i + 1$ 个请求之前完成。电梯的容量很小，在任何时刻，它们必须为空或者恰好搭载一位乘客。此外，每个请求都可以由任意一部电梯完成。

我们希望构建一个智能系统，因此想要最小化电梯空驶的总楼层数。更准确地说，如果一部电梯从第 $p$ 层空驶到第 $q$ 层（即不搭载乘客），那么我们认为它空驶了 $|p - q|$ 层。注意，电梯可以在同一楼层等待任意长时间，而不产生任何额外代价。

遗憾的是，这家酒店有些年头了，而且设备只有 64 MB 内存！不过，我们知道你是一位出色的程序员，所以这对你来说应该不成问题。

请编写一个程序 lifts，计算出能将电梯空驶的总楼层数最小化的最优调度方案。

输入格式

标准输入的第一行包含整数 $n$ 和 $k$。接下来的 $n$ 行，每行包含两个整数 —— 对应请求的 $(l, r)$。

输出格式

在标准输出的唯一一行中，输出电梯空驶的最小总楼层数。

3 2
5 20
8 100
2 80

12

提示

样例解释

电梯 $1$ 初始位于第 $5$ 层，电梯 $2$ 初始位于第 $8$ 层。

电梯 $1$ 空驶 $0$ 层，搭载第一位乘客到达第 $20$ 层。

电梯 $1$ 继续空驶 $12$ 层，搭载第二位乘客到达第 $100$ 层。

电梯 $2$ 空驶 $0$ 层，搭载第三位乘客到达第 $80$ 层。

电梯空驶的总楼层数为 $0 + 12 + 0 = 12$。

数据范围

• $1 \le n \le 10\,000$
• $1 \le k \le \min(30, n)$
• $1 \le l, r \le 10^9$

子任务

翻译由 DeepSeek V4 Pro 完成