#include <fstream>
#define INF 9999999
#define GMAX 1005
#define WMAX 5005
#define MIN(a,b) (((a)<(b))?(a):(b))

using namespace std;

int d[GMAX][WMAX], i ,j, c[GMAX], e[GMAX], mn = 99999999, g1, w, cmax,ver;

int main()
{
    ifstream f("energii.in");
    ofstream g("energii.out");
    f>>g1>>w;

    for(i=1;i<=g1;i++)
    {
        f>>e[i];
        f>>c[i];
        if(cmax<e[i])
            cmax=e[i];
    }

    for(i=1;i<=g1;i++)
        for(j=1; j<=w; j++)
            d[i][j] = INF;

    for(i=1;i<=g1;i++)

    for(i=1;i<=g1;i++)
        for(j=1;j<=w;j++)
        {
        d[i][j]=d[i-1][j];
         if(e[i]<=j)
            d[i][j] = d[i-1][j-e[i]]+c[i];
        }

    for(i=1;i<=g1;i++)
        if(e[i]>w && c[i]<d[g1][w])
            d[g1][w]=c[i];

    for(i=1;i<=g1;i++)
        {
        for(j=1;j<=w;j++)
            g<<d[i][j]<<" ";
        g<<"\n";
        }

    for(i=1;i<=g1;i++)
        ver=ver+e[i];

    if(ver<w)
        g<<-1;
    else
        g<<d[g1][w];
}