#include <bits/stdc++.h>
using namespace std;
int  w[5001], p[5001], dp[2][10001], n, G;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
    int i,g,aux,u,v;
    fin>>n>>G;
    for(i=1; i<=n; i++)
        fin>>w[i]>>p[i];
    u=0;
    v=1;
    for(i=1; i<=n; i++)
        {
            for(g=1; g<=G; g++)
        {
            dp[v][g]=dp[u][g];///nu iau obiectul [i]
            if(g>=w[i]) ///incerc sa iau obiectul [i]
            {
                aux=dp[u][g-w[i]]+p[i];
                if(aux>dp[v][g])
                    dp[v][g]=aux;
            }
        }
        u=1-u;
        v=1-v;
        }
    fout<<dp[u][G];
    return 0;
}