#include<bits/stdc++.h> #defind int long long using namespace std; int n,s,w[10001],l[10001],f[10001],sum[10001],m=LONG_LONG_MAX; int opt(int L,int R) { int W=0,h=0; for(int i=L;i<=R;i++) h=max(l[i],h); return sum[R]-sum[L-1]>s?m:h; } signed main() { cin>>n>>s; for(int i=1;i<=n;i++) cin>>w[i]>>l[i],sum[i]=sum[i-1]+w[i]; for(int i=1;i<=n;i++) { f[i]=m; for(int j=i-1;j>=0;j--) { if(opt(j+1,i)>s) break; f[i]=min(f[i],f[j]+opt(j+1,i)); } } cout<<f[n]; }