#include <iostream>
#include <fstream>


using namespace std;

ifstream f("valori.in");
ofstream gout("valori.out");

int main()
{   int n,ca,j,s,g,vm=0;
    f>>n;
    f>>ca;
    int d[2][ca],a[n][2];
    for(int i=1;i<=n;i++)
    {
        j=0;
        f>>a[i][j];
        j=1;
        f>>a[i][j];

    }
    for(int i=0;i<j;i++)
        d[0][i%2]=0;
    for(int i=1;i<=n;i++)
    {
        for(j=0;j<=ca;j++)
        {   g=a[i][1];
            s=a[i][0]+d[(i-1)%2][j-g];
            if(j>=a[i][1])
            {
              if(s>d[(i-1)%2][j])
                 d[i%2][j]=s;
                 else
                  d[i%2][j]=d[(i-1)%2][j];
            }
             else
                d[i%2][j]=d[(i-1)%2][j];

        }
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=ca;j++)
        {
            gout << d[i%2][j] << " ";
        }
        gout << '\n';
    }
    j=ca;
    for(int i=n;i>0;i--)
    {
        if(d[i%2][j]!=d[(i-1)%2][j])
            {
             { vm=vm+a[i][0];
               j=j-a[i][1];
               gout<<"includem elementul  "<<i<<'\n';
             }

            }

    }
    gout<<'\n'<<vm;


    return 0;
}

 /**
 Notite mai putin relevante
 v =a[p][q] este valoare
 g= a[p][q+1] este greutatea
  declarare primul rand 0
  verificare daca :
  s=v+d[i-1][j-g]
  if(g==d[i][j]) ajungem la greutatea de indexare
      if( s> d[i-1][j]) comparat suma vaolrii obiectului si a elementului posibil incadrat in rucsac
         d[i][j]= s;
         else
          d[i][j]=d[i-1][j];

 */