#include <bits/stdc++.h>

using namespace std;

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

int n, g;
int dyn[2][5010];

int main()
{
    inf>>n>>g;
    int x, y;
    inf>>x>>y;
    dyn[1][x]=y;
    for(int i=2; i<=n; i++)
    {
        int w=(i&1);
        inf>>x>>y;
        for(int j=1; j<=g; j++)
        {
            if(j<x)
                dyn[w][j]=dyn[w^1][j];
            else
                dyn[w][j]=max(y+dyn[w^1][j-x], dyn[w^1][j]);
        }
    }
    outf<<dyn[n&1][g];

    return 0;
}