#include <iostream>
#include <fstream>

using namespace std;

int N, G, W[10000], P[10000], dp[5000][10000] = {0};

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

    f >> N >> G;

    for (int i = 1; i <= N; i ++) f >> W[i] >> P[i];

    for (int i = 1; i <= N; i ++)
        for (int j = 1; j <= G; j++){
            if (W[i] <= j)
                dp[i][j] = max (dp[i-1][j], dp[i-1][j - W[i]] + P[i]);
                else dp[i][j] = dp[i-1][j];
        }

    g << dp[N][G];

    return 0;
}