#include <bits/stdc++.h>
#define N 1003
using namespace std;

ifstream fin ("rucsac.in");
ofstream fout("rucsac.out");

int n, gmax, g[N], v[N], p[N][N];

void cit(){

    fin>>n>>gmax;
    for(int i=1; i<=n; ++i)
        fin>>g[i]>>v[i];
}

void afis(){

    int i, j;

    cout<<"   ";
    for(i=1; i<=gmax; ++i)
        cout<<i<<" ";
    cout<<"\n";
    for(i=1; i<=n; ++i)
    {
        cout<<i<<": ";
        for(j=1; j<=gmax; ++j)
            cout<<p[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"\n\n";
}

int main()
{
    cit();

    int i,x, j;

    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=gmax; ++j)
            if(g[i]<=j and p[i-1][j] < p[i-1][j-g[i]]+v[i])
            {
                p[i][j]=p[i-1][j-g[i]]+v[i];
            }
            else p[i][j]=p[i-1][j];
        afis();
    }
    fout<<p[n][gmax];
    return 0;
}