Description

为了寻找传说中的Avalon，island派出了 $n$ 个考察队。为了保持island的稳定，island有一个通向外界的大门。

这 $n$ 个考察队都需要出一次门进行考察，其中第 $i$ 支考察队会在 $l_i$ 时刻离开，并且在第 $r_i$ 时刻回来。我们保证这些值都是互不相等的。

每当一支考察队离开时，island的大门会变成开的。但是如果这支考察队得到了钥匙，那么他就可以决定关门或者不关门。同时每一个考察队回来的时候要么门本来就是开的（由于island是已知唯一的生活区，因此island内部人员不会主动为任何人开门），要么他必须拥有一把钥匙把门打开。注意，回来的时候无论有没有钥匙，那么这支考察队都可以选择把门关上。

由于一些奇怪的原因，island的设计者只设计了 $k$ 把钥匙，只能分给 $k$ 支考察队。得到钥匙证明了island上层对考察队的信任，因此考察队不会把钥匙交给任何人。

为了防止island下层居民逃出island，上层希望门处于开的时间越短越好。希望您帮他算出最短门会开多久。

Input Format

第一行是两个正整数 $n,k$

第二行开始共 $n$ 行，每行两个数，描述 $l_i,r_i$

Output Format

一个正整数，表示答案。

5 2
1 9
2 10
3 5
7 12
15 17

6

Hint

【样例解释】

④                     ================
③/⑤       -------                              ------
②      -------------------------
①   ========================= 
    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
状态 X  O  O  O  X  X  X  X  O  X  X  X  X  X  O  O 

其中，1、4号考察队会带钥匙。

【数据范围】

对于 $30\%$ 的测试数据，$n \leq 20$

对于 $60\%$的测试数据，$n \leq 200$

对于全部的测试数据，$n \leq 2000$

$1 \leq l_i < r_i\leq 10^9, k \le n$