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

int n,G,g[5005],v[5005];

int D[5005][10001];

void Citire()
{
    ifstream fin("rucsac.in");
    fin>>n>>G;
    for(int i=1;i<=n;i++)
    {
        fin>>g[i]>>v[i];
    }
    fin.close();
}



int main()
{
    Citire();

    for(int i=1;i<=n;i++)
    {
        for(int cw=1;cw<=G;cw++)
        {
            //Mai intai nu il punem
            D[i][cw]=D[i-1][cw];

            //verificam daca il punem ne da o solutie mai buna
            if(cw>=g[i])
                D[i][cw]=max(D[i-1][cw-g[i]]+v[i],D[i][cw]);

        }
    }

    ofstream fout("rucsac.out");
    fout<<D[n][G]<<"\n";
    fout.close();


    return 0;
}