#include <iostream>
#include <fstream>

using namespace std;
ifstream fin  ("energii.in");
ofstream fout ("energii.out");
int w[5003], wp[1003], c[1003];
int main()
{
    int n, W;

    cin >> n >> W;
    for(int i = 1; i <= W; i++)
        w[i] = 50000003;
    for(int i = 1; i <= n; i++)
    {
        cin >> wp[i] >> c[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = W; j >= 0; j--)
        {
            if(j - wp[i] >= 0)
            w[j] = min(w[j], w[j-wp[i]] + c[i]);
            cout << w[j] << ' ';
        }
        cout << endl;
    }
    if(w[W] == w[W-1])
        cout << -1;
    else
    cout << w[W];
    return 0;
}
/*
4
11
2 4
2 3
8 9
1 2
*/