#include <iostream>
#include <fstream>
using namespace std;

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

int Dp[2][10005], n, G, P[5005], W[5005];

int main()
{
    f >> n >> G;
    int ind = 0;
    for(int i = 1; i <= n; ++i)
        f >> W[i] >> P[i];
        for(int i = 1; i <= n; ++i)
        {
            ind = 1 - ind;
        for(int j = 1; j <= G; ++j)
        if(j-W[i] >= 0)
            Dp[ind][j] = max(Dp[1-ind][j], Dp[1-ind][j-W[i]] + P[i]);
        else Dp[ind][j] = Dp[1-ind][j];
        }
    g << Dp[ind][G];
}