#include <fstream>
#include <bitset>

using namespace std;

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

int gmax , n , g[5001] , c[5001] ,cmax[5001] , maxx;
bitset<1001> viz[5001];

void rucsac()
{
    int maxi , pmax;
    for(int i = 1 ; i <= gmax ; ++i) {
        maxi = 0;
        for(int j = 1 ; j <= n ; ++j) {
            if((g[j] <= i && viz[i - g[j]][j] == 0 && cmax[i - g[j]] > 0) || g[j]==i)
                if(c[j] + cmax[i - g[j]] > maxi) {
                    maxi = c[j] + cmax[i - g[j]];
                    pmax = j;
                }
        }
        if(maxi > 0) {
            for(int j = 1 ; j <= n ; ++j)
                viz[i][j] = viz[i - g[pmax]][j];
            viz[i][pmax] = 1;
            cmax[i] = maxi;
        }
    }
}
int main()
{
    fi >> n >> gmax;
    for(int i = 1 ; i <= n ; ++i)
        fi >> g[i] >> c[i];

    rucsac();

    for(int i = 1 ; i <= gmax ; ++i){
        maxx = max(cmax[i] , maxx);
    }

    fo << maxx;
    return 0;
}