#include <iostream>
#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int NMAX = 5001, GMAX = 10001;
int profitMax[GMAX];

int main()
{
    int n, G, ans = 0;
    f >> n >> G;
    for (int i = 1; i <= n; i++)
    {
        int gCrt, pCrt;
        f >> gCrt >> pCrt;
        for (int w = G; w >= gCrt; w--)
        {
            profitMax[w] = max(profitMax[w - gCrt] + pCrt, profitMax[w]);
            ans = max(ans, profitMax[w]);
        }
    }
    g << ans;
    return 0;
}