#include <iostream>
#include <fstream>

using namespace std;

int sol[5001][5001]= {0};

void solve(int n, int g, int w[], int p[])
{
    ofstream out("rucsac.out");


    for(int i = 1; i <= g; i++) ///Current weight
    {
        for(int j = 1; j <= n; j++)///Current item
        {

            if(w[j] > i)
                sol[i][j] = sol[i][j - 1];
            else sol[i][j] = max(sol[i][j - 1], p[j] + sol[i - w[j]][j - 1]);
        }
    }
    out<<sol[g][n];
}

int main()
{
    int n,g;

    ifstream f("rucsac.in");


    f>>n>>g;
    int w[5001],p[5001];

    for(int i = 1; i <= n; i++)
    {
        f>>w[i]>>p[i];
    }

    solve(n, g, w, p);

    return 0;
}