Never·island

您一觉醒来，发现已经到了20000年后的未来。

为了寻找传说中的Avalon，island派出了 $n$ 个考察队。为了保持island的稳定，island有一个通向外界的大门。 这 $n$ 个考察队都需要出一次门进行考察，其中第 $i$ 支考察队会在 $l_i$ 时刻离开，并且在第 $r_i$ 时刻回来。我们保证这些值都是互不相等的。 每当一支考察队离开时，island的大门会变成开的。但是如果这支考察队得到了钥匙，那么他就可以决定关门或者不关门。同时每一个考察队回来的时候要么门本来就是开的（由于island是已知唯一的生活区，因此island内部人员不会主动为任何人开门），要么他必须拥有一把钥匙把门打开。注意，回来的时候无论有没有钥匙，那么这支考察队都可以选择把门关上。 由于一些奇怪的原因，island的设计者只设计了 $k$ 把钥匙，只能分给 $k$ 支考察队。得到钥匙证明了island上层对考察队的信任，因此考察队不会把钥匙交给任何人。 为了防止island下层居民逃出island，上层希望门处于开的时间越短越好。希望您帮他算出最短门会开多久。

第一行是两个正整数 $n,k$ 第二行开始共 $n$ 行，每行两个数，描述 $l_i,r_i$

一个正整数，表示答案。

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

6

【样例解释】 ``` ④ ================ ③/⑤ ------- ------ ② ------------------------- ① ========================= 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$