#include <fstream>
#define N 5005
using namespace std;

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

int n, g;
int greutate[N], pret[N];
int dp[2 * N];

int main()
{
    in>>n>>g;

    for(int i = 1; i <= n; ++i)
        in>>greutate[i]>>pret[i];

    dp[0] = 0;
    int sol = 0;

    for(int i = 1; i <= n; ++i)
        for(int j = g - greutate[i]; j >= 0; --j)
            if(dp[j + greutate[i]] < dp[j] + pret[i]){
                dp[j + greutate[i]] = dp[j] + pret[i];
                sol = max(sol, dp[j + greutate[i]]);
            }

    out<<sol;
    in.close();
    out.close();
    return 0;
}