#include <fstream>
using namespace std;

ifstream in("energii.in");
ofstream out("energii.out");
int n_generators , req_energy;
struct values{
    int e , p;
};
values v[1001];
int sol[1001][5001];
int main(){
    in >> n_generators >> req_energy;
    for(int i = 1 ; i <= n_generators ; i++){
        sol[0][i] = -1;
        in >> v[i].e >> v[i].p;
    }
    for(int i = 1 ; i <= n_generators ; i++){
        for(int j = 1 ; j <= req_energy ; j++){
            if(j <= v[i].e){
                if(sol[i - 1][j] > 0)
                    sol[i][j] = min(sol[i - 1][j] , v[i].p);
                else{
                    sol[i][j] = v[i].p;
                }
            }
            else{
                if(sol[i - 1][j - v[i].e] > 0){
                    sol[i][j] = v[i].p + sol[i - 1][j - v[i].e];
                }
            }
        }
    }
    for(int i = 1 ; i <= n_generators ; i++ , out << '\n')
        for(int j = 1 ; j <= req_energy ; j++)
            out << sol[i][j] << ' ';
    if(sol[n_generators][req_energy] == 0)
        out << '-1';
    else
        out << sol[n_generators][req_energy];
}