1 //NOI 2016 D2T1  2 //by Cydiater  3 //2016.9.18  4 #pragma GCC optimize("O2")  5 #include <iostream>  6 #include <cstdio>  7 #include <cstdlib>  8 #include <cstring>  9 #include <string> 10 #include <algorithm> 11 #include <queue> 12 #include <map> 13 #include <ctime> 14 #include <cmath> 15 #include <iomanip> 16 using namespace std; 17 #define ll long long 18 #define up(i,j,n)        for(INT i=j;i<=n;i++) 19 #define down(i,j,n)        for(INT i=j;i>=n;i--) 20 #define FILE "interval" 21 #define INT unsigned int 22 const INT MAXN=1e6+5; 23 const INT oo=0x3f3f3f3f; 24 map<INT,INT> lable; 25 inline INT read(){ 26     char ch=getchar();INT x=0,f=1; 27     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 28     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 29     return x*f; 30 } 31 INT num[MAXN],N,M,top=0,cnt=0,check=0,x,y,v,ans=oo; 32 struct Query{ 33     INT st,nd,len; 34 }q[MAXN]; 35 struct Tree{ 36     INT maxx,delta; 37 }t[MAXN<<3]; 38 namespace solution{ 39     inline bool cmp(Query a,Query b){return a.len<b.len;} 40     inline void downit(INT node){ 41         if(t[node].delta==0)return; 42         t[node<<1].delta+=t[node].delta;t[node<<1|1].delta+=t[node].delta; 43         t[node<<1].maxx+=t[node].delta;t[node<<1|1].maxx+=t[node].delta; 44         t[node].delta=0; 45     } 46     inline void reload(INT node){t[node].maxx=max(t[node<<1].maxx,t[node<<1|1].maxx);} 47     void updata(INT leftt,INT rightt,INT root){ 48         downit(root); 49         if(leftt>y||rightt<x)        return; 50         if(leftt>=x&&rightt<=y){ 51             t[root].maxx+=v; 52             t[root].delta+=v; 53             return; 54         } 55         INT mid=(leftt+rightt)>>1; 56         updata(leftt,mid,root<<1); 57         updata(mid+1,rightt,root<<1|1); 58         reload(root); 59     } 60     void init(){ 61         N=read();M=read(); 62         up(i,1,N){ 63             q[i].st=read();q[i].nd=read(); 64             num[++top]=q[i].st;num[++top]=q[i].nd; 65         } 66         sort(num+1,num+top+1); 67         up(i,1,top)if(!lable[num[i]])lable[num[i]]=++cnt; 68         up(i,1,N){ 69             q[i].len=q[i].nd-q[i].st; 70             q[i].st=lable[q[i].st]; 71             q[i].nd=lable[q[i].nd]; 72         } 73         sort(q+1,q+N+1,cmp); 74     } 75     void slove(){ 76         up(i,1,N){ 77             while(t[1].maxx<M&&check<N){ 78                 check++; 79                 x=q[check].st;y=q[check].nd;v=1; 80                 updata(1,cnt,1); 81             } 82             if(t[1].maxx>=M)ans=min(ans,q[check].len-q[i].len); 83             x=q[i].st;y=q[i].nd;v=-1; 84             updata(1,cnt,1); 85         } 86     } 87     void output(){ 88         if(ans==oo)puts("-1"); 89         else cout<<ans<<endl; 90     } 91 } 92 int main(){ 93     //freopen(FILE".in","r",stdin); 94     //freopen(FILE".out","w",stdout); 95     //freopen("input.in","r",stdin); 96     using namespace solution; 97     init(); 98     slove(); 99     output();100     return 0;101 }