#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int seg,scg,l,a[1002][10001],b[1002][10001],x,g,w,eg[10001],cg[10001];
int main()
{
    fin>>g;
    fin>>w;
    l=0;
    seg=scg=0;
    for(int i=1;i<=g;i++)
    {
        fin>>eg[i]>>cg[i];
        if(seg<w)
        {seg=seg+eg[i];
         scg=scg+cg[i];}
    }
    for(int j=2;j<=seg;j++)
    {a[1][j]=eg[1];
     b[1][j]=cg[1];}
    for(int i=2;i<=g;i++)
    {
        for(int j=1;j<=seg;j++)
        if(j>eg[i])
        {
                    x=j;
                    if(a[i-1][j-eg[i]]==0)
                        {
                            while(a[i-1][x-eg[i]]==0)
                                x++;
                        }
                    a[i][j]=eg[i]+a[i-1][x-eg[i]];
                     b[i][j]=cg[i]+b[i-1][x-eg[i]];


        }
        else
        {
            if(a[i-1][j]!=0)
            {
                if(a[i-1][j]<j)
          {
              a[i][j]=eg[i];
              b[i][j]=cg[i];
          }
             else
             {
                 if(b[i-1][j]<cg[i])
                 {
                     b[i][j]=b[i-1][j];
                     a[i][j]=a[i-1][j];
                 }
                 else
                 {
                     a[i][j]=eg[i];
                     b[i][j]=cg[i];
                 }
             }


         }
         else
         {
                a[i][j]=eg[i];
                b[i][j]=cg[i];
                 }

    }
    }
    for(int i=2;i<=g;i++)
    {
        for(int j=2;j<=seg;j++)
            cout<<b[i][j]<<"  ";
        cout<<endl;
    }
    x=seg;
while(a[g][x]>w&&x>1)
    x--;
fout<<b[g][x++];
    return 0;
}