#include <fstream>

#define inf 10000000
#define nmax 50001
using namespace std;


ifstream f("energii.in");
ofstream g("energii.out");

int G, w, e[1001], c[1001];
int mini[1001][1001];
int main()
{ int i, j, s=0;
    f>>G>>w;
    for(i=1; i<=G; i++)
        { f>>e[i]>>c[i];
          s+=e[i];
        }
        for(i=0;i<=G;i++)
            for(j=0;j<=w;j++)
              mini[i][j]=inf;

    for(i=1;i<=G;i++)
        for(j=0;j<=w;j++)
          {
              if(e[i]<j)
               mini[i][j]=min(mini[i-1][j],mini[i-1][j-e[i]]+c[i]);
             else
                mini[i][j]=min(mini[i-1][j],c[i]);
          }
        for(i=0;i<=G;i++)
            {for(j=0;j<=w;j++)
              g<<mini[i][j]<<' ';
              g<<'\n';
            }
  }