Description

在数轴上有n个闭区间 \([l_1,r_1],[l_2,r_2],\ldots ,[l_n,r_n]\) 。现在要从中选出m个区间,使得这m个区间共同包含至少一个位置。换句话说,就是使得存在一个x,使得对于每一个被选中的区间 \([l_i,r_i]\) ,都有 \(l_i\le x\le r_i\)

对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 \([l_i,r_i]\) 的长度定义为 \(r_i?l_i\) ,即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案,输出−1。

Input:


第一行包含两个正整数n,m用空格隔开,意义如上文所述。保证 \(1\le m\le n\)
接下来n行,每行表示一个区间,包含用空格隔开的两个整数 \(l_i\)\(r_i\) 为该区间的左右端点。
\(N\le 500000,M\le 200000,0\le l_i\le r_i\le 10^9\)

Output:


只有一行,包含一个正整数,即最小花费。

Sample Input:


Sample Output:


题解:


先离散化。

把所有区间排一下序,然后尺取,每一次在线段树中区间加1或减1。

若最大值不小于m则更新答案。