题目描述

王老师的房间里有一个火炉，为了节省燃料一般只会在有客人来的时候才会打开。

就在今天，王老师历时 一坤年 终于学会了 坤拳。王老师的朋友们听到这个消息之后都高兴坏了，纷纷来王老师家里道贺。

来道贺的一共有 $n$ 个人，因为只是道贺，所以不会呆太久。第 $i$ 个人会在时间 $t_i$ 到达并在时间 $t_i +1$ 离开，不会有两人同时过来道贺。在接待客人的时候，王老师会把火炉点燃，但是王老师只有 $k$ 根火柴了，也就是说火炉只能点燃 $k$ 次。

为了节省燃料，王老师想让火炉点燃的时间尽可能的缩短，现在请你来计算炉子最少要燃烧多长时间。

输入格式

第一行输入两个正整数 $n,k$接下来 $n$ 行每行输入一个整数 $t_i$

$1≤k≤n≤10^5$

$1≤t_i ≤10^9 且 t_i​ <t_i+1$ ​

输出格式

在一行中输出一个正整数代表火炉燃烧的时长

样例输入 1

3 2
1
3
6

样例输出 1

4

样例输入 2

3 1
1
2
6

样例输出 2

6

提示/说明

样例1解释

在时间 1 打开，在时间 4 关闭；在时间 6 打开，在时间 7 关闭；总时间 =(4−1)+(7−6)=4

数据范围

测试点编号 限制 1−8 n≤20 9−13 n≤5000 14−20 无限制