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

const int NMAX = 5000;
const int CMAX = 10000;
int costmaxim;
int n;
int sol;

int P[NMAX],C[NMAX];
int S[2][CMAX];
int l;





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];

    }


    S[0][0] = 0;
    l = 0;
    for(int i=1 ;i<=n; i++, l = 1 -l)
        for(int j=0; j<=costmaxim; j++)
        {
            S[1-l][j] = S[l][j];

            if(C[i] <= j)
            {
                S[1-l][j] = max(S[1-l][j],S[l][j - C[i]]+ P[i]);

            }



        }

        fout << S[l][costmaxim];







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



    return 0;
}