#include <iostream>
#include <fstream>

#define inf 10000000

using namespace std;

int g[1005],w[1005],rez[5005];
   int G,W;

int main()
{
  ifstream f("energii.in");
  ofstream gout("energii.out");


  f >> G >> W;

   for (int i=1;i<=G;++i )
     f >> g[i] >> w[i];

   for (int i=1;i<=W;++i)
     rez[i] = inf;

for (int i=1; i<=W; ++i)
     cout << rez[i] << ' ';

   for (int i=1; i<=G;++i)
   {
       for (int j=W;j>=0;--j)
       {
           if ( j-g[i] >= 0 )
           {
            if (rez[j] > rez[j-g[i]] + w[i] ) rez[j] = rez[j-g[i]] + w[i];
           }
               else rez[j] = min(rez[j],w[i]);
       }
       cout << i << endl;
   }

   for (int i=1; i<=W; ++i)
     cout << rez[i] << ' ';

   if (rez[W] != inf)  gout << rez[W] ; else gout << "-1";

    return 0;
}