#include <stdio.h>#include <algorithm>#include <stdlib.h>#include <string.h>#include <map>#include <set>#define ll long long#define clr(x,y) memset(x,y,sizeof(x))using namespace std;const ll inf = 1000000000000000000LL;const int N=200000;ll a[N],b[N],sum[N];ll q[N],dp[N],val[N];int i,j;ll m,n;multiset<ll> st;bool ac(ll x){ clr(val,-1); st.clear(); ll s=0,t=0,j=0; for(int i=1;i<=n;i++){ while(sum[i]-sum[j]>x) j++; while(sum[i]-sum[q[s]]>x){ st.erase(st.find(val[q[s]])); val[q[s]]=-1; s++; } while(t>s&&a[i]>a[q[t-1]]){ st.erase(st.find(val[q[t-1]])); val[q[t-1]]=-1; t--; } if(t>s){ st.erase(st.find(val[q[t-1]])); val[q[t-1]]=dp[q[t-1]]+a[i]; st.insert(val[q[t-1]]); } q[t++]=i; ll temp=inf; if(st.size()) temp=min(temp,*st.begin()); temp=min(temp,dp[j]+a[q[s]]); dp[i]=temp; st.insert(inf); val[i]=inf; } if(dp[n]<=m) return 1; else return 0;}ll solve(){ ll l=0,r=inf; for(int i=1;i<=n;i++) l=max(l,a[i]); while(r-l>1){ ll mid=(l+r)/2; if(ac(mid)) r=mid; else l=mid; } if(ac(l)) return l; else return r;}int main(){ while(scanf("%lld%lld",&n,&m)!=EOF){ for(i=1;i<=n;i++){ scanf("%lld%lld",&a[i],&b[i]); sum[i]=sum[i-1]+b[i]; } printf("%lldn",solve()); }return 0;}
