#include <iostream>
#include <fstream>

using namespace std;

int N, G, W[10000], P[10000], dp[2][10001] = {0}, curr, ant, i;

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

    f >> N >> G;

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

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

    g << dp[N][G];

    return 0;
}