#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,i,g,w[5001],p[5001],u,v;
long long aux,dp[2][10001];
/// 10.000*8=80.000+4*10.000= 120.000
int main()
{
    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];
            if(w[i]<=g)
            {
                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;
}