#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int limit,n,N,front=0,sbtroot,l,f,a[50001],b[50001],LAST[50001],g[50001];
LL q[210001],F[50001],sB[50001],A[50001],B[50001],LEFT,RIGHT,MID;
struct node
{int a,b,id;
}na[50001],nb[50001];
struct tree
{int l,r,s;
 LL key;
}sbt[100001];
int cmpa(node a,node b){return a.a>b.a;}
int cmpb(node a,node b){return a.b>b.b;}
void lr(int& x)
{int y=sbt[x].r;
 if(y==0) return;
 sbt[x].r=sbt[y].l;
 sbt[y].l=x;
 sbt[y].s=sbt[x].s;
 sbt[x].s=sbt[sbt[x].l].s+sbt[sbt[x].r].s+1;
 x=y;
}
void rr(int& x)
{int y=sbt[x].l;
 if(y==0) return;
 sbt[x].l=sbt[y].r;
 sbt[y].r=x;
 sbt[y].s=sbt[x].s;
 sbt[x].s=sbt[sbt[x].l].s+sbt[sbt[x].r].s+1;
 x=y;
}
void maintain(int& root,bool flag)
{if(!root) return;
 if(flag)
 {if(sbt[root].l&&sbt[sbt[root].l].l&&(!sbt[root].r||sbt[sbt[sbt[root].l].l].s>sbt[sbt[root].r].s)) rr(root);
  else if(sbt[root].l&&sbt[sbt[root].l].r&&(!sbt[root].r||sbt[sbt[sbt[root].l].r].s>sbt[sbt[root].r].s)){lr(sbt[root].l);rr(root);}
  else return;
 }
 else
 {if(sbt[root].r&&sbt[sbt[root].r].r&&(!sbt[root].l||sbt[sbt[sbt[root].r].r].s>sbt[sbt[root].l].s)) lr(root);
  else if(sbt[root].r&&sbt[sbt[root].r].l&&(!sbt[root].l||sbt[sbt[sbt[root].r].l].s>sbt[sbt[root].l].s)){rr(sbt[root].r);lr(root);}
  else return;
 }
 maintain(sbt[root].l,true);
 maintain(sbt[root].r,false);
 maintain(root,true);
 maintain(root,false);
}
void Insert(int& root,LL x)
{if(!root)
 {root=++front;
  sbt[root].key=x;
  sbt[root].s=1;
 }
 else
 {++sbt[root].s;
  Insert(x<=sbt[root].key?sbt[root].l:sbt[root].r,x);
  maintain(root,x<=sbt[root].key);
 }
}
int Delete(int& root,LL x)
{--sbt[root].s;
 if(x==sbt[root].key||(x<sbt[root].key&&!sbt[root].l)||(x>sbt[root].key&&!sbt[root].r))
 {LL k=sbt[root].key;
  if(!sbt[root].l) root=sbt[root].r;
  else if(!sbt[root].r) root=sbt[root].l;
  else sbt[root].key=Delete(sbt[root].r,-1);
  return k;
 }
 else return Delete(x<=sbt[root].key?sbt[root].l:sbt[root].r,x);
}
LL find_min(int root)
{if(!root) return 2147000000000000ll;
 if(sbt[root].l!=0) return find_min(sbt[root].l);
 return sbt[root].key;
}
bool work(LL L)
{int i,t;
 g[1]=1;
 for(i=2;i<=n;i++)
 {g[i]=g[i-1];
  while(sB[i]-sB[g[i]-1]>L) g[i]++;
 }
 for(i=1;i<=n;i++)
 {F[i]=F[i-1]+A[i];
  t=i-1;
  while(f>l&&A[q[f]]<=A[i])
  {Delete(sbtroot,A[t]+F[q[f]]);
   t=q[f];
   f--;
  }
  if(f>l&&A[i]>A[t]){Delete(sbtroot,F[q[f]]+A[t]);Insert(sbtroot,F[q[f]]+A[i]);}
  if(A[i-1]>A[i])
  {q[++f]=i-1;
   Insert(sbtroot,A[i]+F[i-1]);
  }
  while(f>l&&sB[i]-sB[q[l+1]]>L)
  {if(l==f-1) Delete(sbtroot,A[i]+F[q[l+1]]);
   else Delete(sbtroot,A[q[l+2]]+F[q[l+1]]);
   l++;
  }
  F[i]=min(F[i],find_min(sbtroot));
  if(f>l&&q[l+1]!=g[i]-1) F[i]=min(F[i],F[g[i]-1]+A[q[l+1]]);
  if(f<=l) F[i]=min(F[i],F[g[i]-1]+A[i]);
 }
 return F[n]<=limit;
}
void work_AB()
{int i,j,now,last,first;
 for(i=1;i<=n;i++)
 {na[i].a=a[i];
  na[i].b=b[i];
  na[i].id=i;
  nb[i]=na[i];
  RIGHT+=b[i];
 }
 sort(na+1,na+n+1,cmpa);
 sort(nb+1,nb+n+1,cmpb);
 now=last=1;
 for(i=1;i<=n;i++)
 {if(nb[i].b>na[now].a) LAST[nb[i].id]=0;
  else
  {while(l<=n&&nb[i].b<=na[now].a)
   {last=max(last,na[now].id);
    now++;
   }
   now--;
   LAST[nb[i].id]=last;
  }
 }
 N=0;
 first=last=1;
 for(i=1;i<=n;i++)
 {last=max(last,LAST[i]);
  if(i==last)
  {N++;
   for(j=first;j<=i;j++)
   {A[N]=max(A[N],(LL)a[j]);
    B[N]+=b[j];
   }
   first=last=i+1;
   LEFT=max(LEFT,B[N]-1);
  }
 }
 for(i=1;i<=N;i++) sB[i]=sB[i-1]+B[i];
 n=N;
}
void work_ans()
{while(LEFT+1<RIGHT)
 {MID=(LEFT+RIGHT)/2;
  if(work(MID)) RIGHT=MID;
  else LEFT=MID;
 }
}
int main()
{cin>>n>>limit;
 int i;
 for(i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
 work_AB();
 work_ans();
 cout<<RIGHT;
 return 0;
}