#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int NMAX = 5001, GMAX = 10001;
int n, G, weight[NMAX], profit[NMAX], dp[2][GMAX];

int main()
{
    fin >> n >> G;
    for(int i = 1; i <= n; i++)
        fin >> weight[i] >> profit[i];
    for(int i = 1; i <= n; i++)
    {
        for(int w = weight[i]; w <= G; w++)
            dp[1][w] = max(dp[1][w], dp[0][w - weight[i]] + profit[i]);
        memcpy(dp[0], dp[1], sizeof(dp[1]));
    }
    fout << *max_element(dp[0], dp[0] + GMAX);

    fin.close();
    fout.close();
    return 0;
}