#include <iostream>
#include<fstream>
#include<vector>

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

int main()
{
    int i,n,g,capacitate,obiect;

    fin>>n>>g;

    vector<int> greutate(n+1), valoare(n+1);

    for(i=1;i<=n;i++)
        fin>>greutate[i]>>valoare[i];

    vector<vector<int> > rezolvare(n+1, vector<int>(g+1));
    for(obiect=1;obiect<=n;obiect++) {
        for(capacitate=1;capacitate<=g;capacitate++) {
                rezolvare[obiect][capacitate]=rezolvare[obiect-1][capacitate];

            if(capacitate>=greutate[obiect])
                rezolvare[obiect][capacitate]=max(rezolvare[obiect-1][capacitate],rezolvare[obiect-1][capacitate-greutate[obiect]]+valoare[obiect]);
        }
    }

    fout << rezolvare[n][g];



    return 0;
}