#include <fstream>

using namespace std;

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

struct obiect
{
    int g, p;
} v[5005];

int n, G, dp[5005][10005];

int main()
{
    fin>>n>>G;
    for(int i=1; i<=n; i++)
        fin>>v[i].g>>v[i].p;

    for(int capacitate=1; capacitate<=G; capacitate++)
        dp[0][capacitate]=0;

    for(int i=1; i<=n; i++)
        for(int capacitate=0; capacitate<=G; capacitate++)
    {
        //nu folosesc obiectul i => e solutia de la pasul i-1
        dp[i][capacitate]=dp[i-1][capacitate];

        //folosesc obiectul i, deci trebuie sa rezerv v[i].g unitati in rucsac
        //inseamna ca inainte trebuie sa ocup maxim capacitate-v[i].g unitati

        int aux=0;

        if(capacitate-v[i].g>=0)
            aux=dp[i-1][capacitate-v[i].g]+v[i].p;

        dp[i][capacitate]=max(dp[i][capacitate], aux);
    }

    fout<<dp[n][G];

    fout.close();

    return 0;
}