#include <iostream>
#include <fstream>
using namespace std;
int a[1004][1005],g[1004],c[1005];
ifstream fin("energii.in");
ofstream fout("energii.out");
int n,sol;
void R()
{
    fin>>n>>sol;
    for(int i=1; i<=n; i++)
    fin>>g[i]>>c[i];
}

void Rez()
{
    int i,j;
    for(i=1; i<=n; i++)
    for(j=1; j<=sol; j++)
    a[i][j]=2000000000;

    for(i=1; i<=g[1]; i++)
    a[1][i]=c[1];

    for(i=2; i<=n; i++)
    for(j=1; j<=sol; j++)
     if(g[i]<j)
            a[i][j]=min(a[i-1][j],a[i-1][j-g[i]]+c[i]);
     else
            a[i][j]=min(a[i-1][j],c[i]);

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=sol; j++)
        cout<<a[i][j]<<"   ";
        cout<<"\n";
    }

    fout<<a[n][sol]<<"\n";
}

int main()
{
    R();
    Rez();
    return 0;
}