#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=0; i<n; i++)
    {
        fin >> C[i] >> P[i];

    }


    for(int i=0 ;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-1][j], D[i-1][j-C[i]] +P[i]);
            }
        }


    }

    fout << D[n-1][costmaxim];

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



    return 0;
}