在数轴上有 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 <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 500050

#define ls p<<1

#define rs p<<1|1

int n,m,turn[N<<1],maxn;

int t[N<<3],add[N<<3];

struct A {

    int l,r,lx,rx;

}q[N];

bool cmp1(const A &x,const A &y) {return x.r-x.l<y.r-y.l;}

int p[N<<1];

inline void pushup(int p) {

    t[p]=max(t[ls],t[rs]);

}

inline void pushdown(int p) {

    int d;

    if(d=add[p]) {

        t[ls]+=d; t[rs]+=d;

        add[ls]+=d; add[rs]+=d;

        add[p]=0;

    }

}

void update(int l,int r,int x,int y,int v,int p) {

    if(x<=l&&y>=r) {

        t[p]+=v; add[p]+=v;

        return ;

    }

    pushdown(p);

    int mid=(l+r)>>1;

    if(x<=mid) update(l,mid,x,y,v,ls);

    if(y>mid) update(mid+1,r,x,y,v,rs);

    pushup(p);

}

int query(int l,int r,int x,int y,int p) {

    if(x<=l&&y>=r) return t[p];

    pushdown(p);

    int mid=(l+r)>>1,re=0;

    if(x<=mid) re=max(re,query(l,mid,x,y,ls));

    if(y<mid) re=max(re,query(mid+1,r,x,y,rs));

    pushup(p);

    return re;

}

int main() {

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

    int i,x,y;

    for(i=1;i<=n;i++) {

        scanf("%d%d",&q[i].l,&q[i].r);

        p[i]=q[i].l,p[i+n]=q[i].r;

    }

    sort(p+1,p+2*n+1);

    int j=0;p[0]=5343453;

    for(i=1;i<=n;i++) {

        q[i].lx=lower_bound(p+1,p+n+n+1,q[i].l)-p;

        q[i].rx=lower_bound(p+1,p+n+n+1,q[i].r)-p;

    }

    maxn=2*n;

    sort(q+1,q+n+1,cmp1);

    //for(i=1;i<=n;i++) printf("%d %d\n",turn[q[i].l],turn[q[i].r]);

    int l=1,r=0,ans=1<<30;

    while(r<n) {

        while(t[1]<m&&r<n) r++,update(1,maxn,q[r].lx,q[r].rx,1,1);

        if(t[1]<m) break;

        while(t[1]>=m&&l<n) update(1,maxn,q[l].lx,q[l].rx,-1,1),l++;

        ans=min(ans,q[r].r-q[r].l-q[l-1].r+q[l-1].l);

    }

    printf("%d\n",ans<(1<<30)?ans:-1);

}