题目描述

数轴上放着 $n$ 个闭区间,编号从 $1$ 到 $n$,第 $i$ 个闭区间记为 $[l_i,r_i]$。

现在要从里面挑出 $m$ 个区间,要求这 $m$ 个区间共同覆盖至少一个位置。也就是说,存在某个 $x$,使得对每个被选中的区间 $[l_i,r_i]$ 都满足 $l_i \leq x \leq r_i$。

一个合法选取方案的花费定义为:被选中区间里最长的长度减去最短的长度。区间 $[l_i,r_i]$ 的长度规定为 $(r_i-l_i)$,即右端点的值减去左端点的值。

请求出所有合法方案中最小的花费。如果根本不存在合法方案,输出 $-1$。

输入格式

第一行包含两个整数,分别代表 $n$ 和 $m$。

第 $2$ 到第 $(n + 1)$ 行,每行两个整数表示一个区间,第 $(i + 1)$ 行的整数 $l_i, r_i$ 分别代表第 $i$ 个区间的左右端点。

输出格式

输出一行一个整数表示答案。

样例

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

2

提示

样例解释

当 $n=6$,$m=3$ 时,花费最小的方案是选取 $[3,5],[3,4],[1,4]$ 这三个区间,它们共同包含了位置 $4$,所以是合法的。其中最长的区间是 $[1, 4]$,最短的区间是 $[3, 4]$,所以花费是 $(4 - 1) - (4 - 3) = 2$。

数据规模与约定

对于全部的测试点,保证 $1 \leq m \leq n$,$1 \leq n \leq 5 \times 10^5$,$1 \leq m \leq 2 \times 10^5$,$0 \leq l_i \leq r_i \leq 10^9$。