题目描述

你受雇为一家酒店设计一套电梯系统。

酒店里一共有 $k$ 部电梯，你可以在一开始任意选择它们所在的楼层。

一天中会依次出现 $n$ 个请求，第 $i$ 个请求由一对整数 $(l_i,r_i)$ 描述，表示有人在第 $l_i$ 层，想要前往第 $r_i$ 层。

顾客不喜欢等待，因此这些请求必须按顺序完成。更形式化地说：

• 第 $i$ 个请求必须在第 $i+1$ 个请求开始前完成。
• 每个请求都可以由任意一部电梯来处理。
• 每部电梯在任意时刻要么为空载，要么只载着一名乘客。
• 电梯可以在任意楼层等待任意久，等待本身不产生代价。

我们希望尽量减少电梯空载移动的总楼层数。

更准确地说，如果某部电梯在没有乘客的情况下从第 $p$ 层移动到第 $q$ 层，那么这次空载移动的代价记为：

请你求出完成所有请求所需的最小空载移动总代价。

输入格式

第一行包含两个整数 $n,k$，分别表示请求个数和电梯数量。

接下来 $n$ 行，每行两个整数 $l_i,r_i$，表示一个请求。

输出格式

输出一行一个整数，表示最小空载移动总代价。

数据范围

• $1\le n\le 10^4$
• $1\le k\le \min(30,n)$
• $1\le l_i,r_i\le 10^9$

子任务

只有通过某个子任务的全部测试点，才能获得该子任务的分数。

样例

输入

3 2
5 20
8 100
2 80

输出

12

样例说明

一种最优方案如下：

• 电梯 1 初始在第 $5$ 层；
• 电梯 2 初始在第 $8$ 层。

处理过程：

1. 电梯 1 处理请求 $(5,20)$，空载移动 $0$ 层。
2. 电梯 1 再处理请求 $(8,100)$，需要先从 $20$ 层空载移动到 $8$ 层，代价为 $|20-8|=12$。
3. 电梯 2 处理请求 $(2,80)$，将它的初始楼层设为 $2$，空载移动 $0$ 层。

总空载代价为：