#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,i,g,w[5001],p[5001],dp[5001][10001],aux;
int main()
{
    fin>>n>>G;

    for(i=1; i<=n; i++)
        fin>>w[i]>>p[i];

    for(i=1; i<=n; i++)
        for(g=1; g<=G; g++)
        {
            dp[i][g]=dp[i-1][g];
            if(w[i]<=g)
            {
                aux=dp[i-1][g-w[i]]+p[i];
                if(aux>dp[i][g])
                    dp[i][g]=aux;
            }
        }
    fout<<dp[n][G];
    return 0;
}