在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。

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

第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n

接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。

N<=500000,M<=200000,0≤li≤ri≤10^9

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

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define N (1000009)

 using namespace std;

 struct Node

 {

     int x,y,len;

     bool operator < (const Node &a) const{return len<a.len;}

 }L[N];

 struct Sgt{int max,add;}Segt[N<<];

 int n,m,b[N],num;

 int getid(int x){return lower_bound(b+,b+num+,x)-b;}

 void Pushdown(int now)

 {

     Segt[now<<].max+=Segt[now].add;

     Segt[now<<|].max+=Segt[now].add;

     Segt[now<<].add+=Segt[now].add;

     Segt[now<<|].add+=Segt[now].add;

     Segt[now].add=;

 }

 void Update(int now,int l,int r,int l1,int r1,int k)

 {

     if (l>r1 || r<l1) return;

     if (l1<=l && r<=r1)

     {

         Segt[now].max+=k;

         Segt[now].add+=k;

         return;

     }

     Pushdown(now);

     int mid=(l+r)>>;

     Update(now<<,l,mid,l1,r1,k);

     Update(now<<|,mid+,r,l1,r1,k);

     Segt[now].max=max(Segt[now<<].max,Segt[now<<|].max);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for (int i=; i<=n; ++i)

     {

         scanf("%d%d",&L[i].x,&L[i].y); L[i].len=L[i].y-L[i].x;

         b[i*-]=L[i].x; b[i*]=L[i].y;

     }

     sort(b+,b+*n+);

     num=unique(b+,b+*n+)-b-;

     sort(L+,L+n+);

     int pos=,cnt=,ans=2e9;

     for (int i=; i<=n; ++i)

     {

         while (pos<n && Segt[].max<m)

         {

             ++pos; ++cnt;

             int x=getid(L[pos].x), y=getid(L[pos].y);

             Update(,,num,x,y,);

         }

         if (Segt[].max>=m) ans=min(ans,L[pos].len-L[i].len);

         int x=getid(L[i].x), y=getid(L[i].y);

         Update(,,num,x,y,-);

     }

     printf("%d\n",ans==2e9?-:ans);

 }