#include <bits/stdc++.h>
using namespace std;

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

int n, w[5001], p[5001], dp[2][10001], G, aux, u, v;
int main()
{
    fin>>n>>G;
    for(int i=1; i<=n; i++)
        fin>>w[i]>>p[i];
    u=0;
    v=1;
    for(int i=1; i<=n; i++)
    {
        for(int g=1; g<=G; g++)
        {
            dp[v][g]=dp[u][g]; ///nu iau obiectul i
            if(g>=w[i]) ///incerc sa iau obiectul
            {
                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];
}