#include<iostream> #include<cstring> using namespace std; int w[100001],h[100001],dp[100001],sum[100001]; int main(){ int n,s; cin>>n>>s; for(int i=1;i<=n;i++){ cin>>w[i]>>h[i]; sum[i]=sum[i-1]+w[i]; } memset(dp,63,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;i++){ int max_=0; for(int j=i;;j--){ if(sum[i]-sum[j-1]>s || j<1){ break; } max_=max(max_,h[j]); dp[i]=min(dp[i],dp[j-1]+max_); } } cout<<dp[n]<<endl; return 0; }