#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int a[100],b[100],s,i,p,c[100],j,m,n,S,k;
int main()
{
    f>>n>>p;
    for(i=1; i<=n; i++)
    {
        f>>c[i];
        f>>a[i];
        S=S+a[i];
    }
    for(i=1; i<=n; i++)
    for(j=S; j>=0; j--)
    if(j!=0 && b[j]!=0 && b[a[b[j]]+a[i]]==0) b[a[b[j]]+a[i]]=i;
     else if(j==0 && b[b[j]+a[i]]==0) b[b[j]+a[i]]=i;
     for(i=S; i>=0; i--){
         s=0;
     if(b[i]!=0) {k=i;while(k!=0){s=s+c[k];k=b[k-a[b[j]]];}}
      if(s<p) g<<i;}
     return 0;
}