#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

const int NMAX = 5000;
const int CMAX = 10000;
int costmaxim;
int n;
int P[NMAX],C[NMAX];
int D[NMAX][CMAX];




int main()
{

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


    fin >> n >> costmaxim;
    for(int i=1; i<=n; i++)
    {
        fin >> C[i] >> P[i];

    }

    D[0][0] = 0;
    for(int i=1 ;i<=n; i++)
    {
        for(int j=0; j<=costmaxim; j++)
        {

            D[i][j] = D[i-1][j];
            if(C[i] <= j)
            {

                D[i][j] = max(D[i][j], D[i-1][j-C[i]] +P[i]);
            }
        }


    }

    fout << D[n][costmaxim];

    fin.close();
    fout.close();



    return 0;
}