#include<bits/stdc++.h> using namespace std; int n,sw,l[10001],w[10001],f[10001],MAX=100000000; int Opt(int x,int y) //返回书在区间(x,y)的最大高度 { int width=0,h=0; for(int i=x; i<=y; i++) { width+=w[i]; h=max(l[i],h) ; } return width>sw ? MAX : h; //不能超出宽度限定 } int main(){ scanf("%d%d",&n,&sw); for(int i=1; i<=n; i++) scanf("%d%d",&w[i],&l[i]); for(int i=1; i<=n; i++) //动态规划 { f[i]=MAX; for(int j=0; j<i; j++) f[i]=min(f[i],f[j]+Opt(j+1,i)); } printf("%d\n",f[n]); return 0; }