P16424 [IATI 2022] Lifts

你受雇为一家酒店建造电梯系统！ 酒店有 $k$ 部电梯，初始时你可以选择它们分别停在哪一层。一天当中会有 $n$ 个请求，每个请求由一对 $(l, r)$ 描述，表示有人在第 $l$ 层并希望前往第 $r$ 层。 人们不喜欢久等，因此我们要求请求必须依次完成。更确切地说，第 $i$ 个请求必须在第 $i + 1$ 个请求之前完成。电梯的容量很小，在任何时刻，它们必须为空或者恰好搭载一位乘客。此外，每个请求都可以由任意一部电梯完成。 我们希望构建一个智能系统，因此想要最小化电梯空驶的总楼层数。更准确地说，如果一部电梯从第 $p$ 层空驶到第 $q$ 层（即不搭载乘客），那么我们认为它空驶了 $|p - q|$ 层。注意，电梯可以在**同一楼层等待**任意长时间，而不产生任何额外代价。 遗憾的是，这家酒店有些年头了，而且**设备只有 64 MB 内存**！不过，我们知道你是一位出色的程序员，所以这对你来说应该不成问题。 请编写一个程序 `lifts`，计算出能将电梯空驶的总楼层数最小化的最优调度方案。

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

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

### 样例解释 电梯 $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$ ### 子任务 | 序号 | $n$ | 分值 | |:----:|:-------------:|:----:| | $1$ | $\leq 22$ | $5$ | | $2$ | $\leq 250$ | $20$ | | $3$ | $\leq 600$ | $10$ | | $4$ | $\leq 1250$ | $15$ | | $5$ | $\leq 2500$ | $20$ | | $6$ | 无额外限制 | $30$ | 翻译由 DeepSeek V4 Pro 完成