#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");

int length, necessary, dynamicCost[5002];

int main() {
    for (int i = 0; i < 5002; ++i) {
        dynamicCost[i] = 1002004;
    }
    fin >> length >> necessary;
    for (int iter = 0; iter < length; ++iter) {
        int energy, cost;
        fin >> energy >> cost;
        for (int i = necessary; i > 0 ; --i) {
            dynamicCost[i + energy] = min(dynamicCost[i + energy], dynamicCost[i] + cost);
        }
        dynamicCost[energy] = min(dynamicCost[energy], cost);
    }
    for (int i = 0; i <= necessary; ++i) {
        cout << i << ' ' << dynamicCost[i] << '\n';
    }
    if (dynamicCost[necessary] == 1002004)
        fout << "-1";
    else
        fout << dynamicCost[necessary] << '\n';
    return 0;
}