#include <iostream>#include<cstdio>#include<cstring>using namespace std;int mmin(int a,int b){return a<b?a:b;}int d[1001];int n,pi,res;struct node{ int l,r;}p[1005];int main(){ int i,j,k,p1,p2,len; char t[100]; while(scanf("%d%d",&n,π) != EOF ) { res=k=0; getchar(); for(i=0;i<n;i++) { gets(t); len=strlen(t); int flag=0; for(j=0; j<len; j++) if(t[j]==' ') { flag=1; break; } if(flag) { sscanf(t,"%d%d",&p1,&p2); if(p2-pi<=p1) { res+=p1; continue; } p[k].l=p1; p[k++].r=p2; } else { sscanf(t,"%d",&p1); res+=p1; } } if(res>=pi||k==0) { for(i=0;i<k;i++) res+=p[i].r-pi; printf("%dn",res); continue; } int mm=pi-res; for(i=0; i<=mm; i++) d[i]=100000000; d[0]=0; for(i=0; i<k; i++) { if(p[i].l>=mm) d[mm]=mmin(d[mm],p[i].r-pi-p[i].l); else { for(j=mm-p[i].l;j<=mm;j++)d[mm]=mmin(d[mm],d[j]+p[i].r-pi-p[i].l); for(j=mm; j>=p[i].l; j--) d[j]=mmin(d[j],d[j-p[i].l]+p[i].r-pi-p[i].l); } } if(d[mm]==100000000) { for(i=0; i<k; i++) res+=p[i].l; } else { for(i=0; i<k; i++) res+=p[i].r-pi; res-=d[mm]; } printf("%dn",res); } return 0;}
