#include <fstream>

using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");


int v[5005], u[10005], dp[5005][10005];

int main()
{
    int n, G;

    in >> n >> G;

    for(int i = 1; i <= n; i ++)
        in >> v[i] >> u[i];

    for(int i = 1; i <= n; i ++)
    {
        for(int g = 1; g <= G; g ++)
        {
            dp[i][g] = dp[i - 1][g];

            if(v[i] <= g)
                dp[i][g] = max(dp[i][g], dp[i - 1][g - v[i]] + u[i]);
        }
    }

    out << dp[n][G];

    return 0;
}