当前没有测试数据。

题目描述

小 C 有一堵长度为无穷大的墙，现在她有 $n$ 种给墙刷漆的方案，第 $i$ 种方案刷的是一段区间 $[L_i,R_i]$。你需要帮助她从中选出 $m$ 个区间，满足这 $m$ 个区间的交集不为空（也就是至少存在一个点被 $m$ 个区间包含）。

小C希望这 $m$ 个区间的长度相差不大（区间的长度定义为右端点-左端点的值），换句话说，就是这 $m$ 个区间的最长长度减最短长度的值要尽量小，请你输出这个值。

输入格式

第一行两个整数，$n$ 和 $m$。

接下来 $n$ 行，每行一个区间 $l[i]$ 和 $r[i]$

输出格式

输出一个正整数，表示答案。如果不存在，则输出 $-1$

6 3
3 5
1 2
3 4
2 2
1 5
1 4

2

数据范围

对于 $100\%$ 的数据，$n \le 500000,m \le 200000，0 \le li \le ri \le 10^9$