#include <iostream>

using namespace std;

#define MAX_N 5000
#define MAX_G 10000
int dp[MAX_G][MAX_N];

int main()
{
    int n, g, gro, pro;
    cin >> n >> g;
    for(int i = 1; i <= n; ++i)
    {
        cin >> gro >> pro;
        for(int j = 0; j <= g - gro; ++j)
        {
            dp[i][j + gro] = dp[i - 1][j] + pro;
        }
        for(int j = g - gro + 1; j <= g; ++j)
        {
            dp[i][j] = dp[i - 1][j];
        }
    }

    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; j <= g; ++j)
            cout << dp[i][j] << " ";
        cout << '\n';
    }

    cout << '\n';
    int ans = 0;
    for(int i = 0; i <= g; ++i)
    {
        ans = max(ans, dp[n][i]);
    }
    cout << ans;
    return 0;
}