#include <bits/stdc++.h>

using namespace std;
const int N_MAX = 5000;
const int G_MAX = 10000;

int maxProfit[1 + N_MAX][1 + G_MAX];
int gr[1 + N_MAX], profit[1 + N_MAX];

const int IMPOSSIBLE = -1;
int main()
{
    ifstream in ("rucsac.in");
    ofstream out ("rucsac.out");

    int N, G;
    in >> N >> G;

    for (int i = 1; i <= N; i ++)
       in >> gr[i] >> profit[i];

    for (int i = 1; i <= N; i ++)
       for (int g = 0; g <= G; g ++)
          maxProfit[i][g] = IMPOSSIBLE;

    for (int i = 1; i <= N; i ++) {
       for (int g = 1; g <= G; g ++) {
          maxProfit[i][g] = maxProfit[i - 1][g]; /// cazul în care las afară elementul i
          if (gr[i] <= g && maxProfit[i - 1][g - gr[i]] != IMPOSSIBLE) /// cazul în care consider înăuntru elementul i
            if (maxProfit[i][g] < profit[i] + maxProfit[i - 1][g - gr[i]])
              maxProfit[i][g] = profit[i] + maxProfit[i - 1][g - gr[i]];
       }
    }

    for (int i = 1; i <= N; i ++) {
       for (int g = 1; g <= G; g ++)
          out << maxProfit[i][g] << " ";
       out << "\n";
    }

    int answer = 0;
    for (int g = 1; g <= G;  g ++)
       answer = max (answer, maxProfit[N][g]);
    ////out << answer;

    return 0;
}