该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一条数线上有 $n$ 块布。 第 $i$ $(1\le i\le n)$ 块布覆盖了直线上的区间 $\lbrack L_i ,R_i\rbrack$ 。直线上的一点可能被两块或更多块布覆盖，也可能没有被任何一块布覆盖。

如果直线上的某一点同时被两块布覆盖，则称两块布重叠。

对于没有重叠的两块布 $i,j$，它们之间的距离 $dist(i,j)$ 定义如下：

• 一块布覆盖的所有点 $p$ 和另一块布覆盖的所有点 $q$ 上 $|p-q|$ 的最小值。

对于两两不重叠的 $k$ 块布 $x_1,x_2,...,x_k$，将其得分定义为这些布两两之间的最小距离之和，即 $\sum_{i=1}^{k}\sum_{j=i+1}^{k}dist(x_i,x_j)$。

伞伞会从第 $x_1$ 块布开始选择，第 $i$ 轮他会选择不与 $x_i$ 重叠且 $L_{x_{i+1}} > R_{x_i}$ 的布作为 $x_{i+1}$，重复 $k - 1$ 轮后结束。如果有多块布 $x$ 满足条件，伞伞会选择 $L_x$ 小的那个。如果 $L_x$ 也相同，伞伞会选择 $R_x$ 小的那个。如果 $R_x$ 也相同，则伞伞会从这些 $L_x,R_x$ 均相同的布中选择任意一块布。

你不需要帮伞伞找出从哪块布开始选，你只需要告诉他，按照他的选布方式，从任意一块布开始选，可能的最小得分。注意，你必须保证伞伞最终能够获得 $k$ 块布。

如果从哪块布开始最终都不可能选择出 $k$ 块布，则输出 -1。

输入格式

从文件 dist.in 读入数据。 第一行包含两个整数 $n,k$，表示布的数量和伞伞要选择的布数。

接下来 $n$ 行，每行两个非负整数 $L_i,R_i$ 表示第 $i$ 块布覆盖的区间端点。

输出格式

输出到文件 dist.out。 输出可能的最小得分，如果不存在选够 $k$ 块布的方案，则输出 -1。

6 3
1 12
2 7
5 9
9 13
10 18
15 20

12

2 2
1 5
5 9

-1

20 3
169 748
329 586
529 972
432 520
408 587
138 250
114 656
299 632
755 984
404 772
155 506
832 854
353 465
374 387
384 567
555 631
428 951
104 705
405 530
102 258

374

解释

第 $1$ 组数据 可以让伞伞从第 $2$ 块布开始选，他会依次选第 $2、4、6$ 块布：dist(2,4) = 9−7 = 2，dist(4,6) = 15−13 = 2，dist(2,6) = 15−7 = 8，总和 $= 2 + 2 + 8 = 12$。 （注意是 $3$ 块布两两之间的 $3$ 对距离，不是相邻的 $2$ 段间隙。）

样例 4

见 dist4.in 与 dist4.ans。

样例 5

见 dist5.in 与 dist5.ans。

样例 6

见 dist6.in 与 dist6.ans。

样例 7

见 dist7.in 与 dist7.ans。

样例 8

见 dist8.in 与 dist8.ans。

数据规模与约定

下发文件分别对应子任务 $1,2,3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $2 \leq k\leq n \leq 10^{5},1 \leq L_i \leq R_i \leq 10^8$。

时空限制：$1$ 秒 / $256\,\mathrm{MiB}$。