#include<fstream>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, g, DP[3][10005], px, gx;

void rezolvare(){

    fin>>n>>g;
    fin>>gx>>px;
    for(int i = 0; i <= g; i++)
        if(i - gx >= 0)
            DP[1][i] = px;
    for(int i = 2; i <= n; i++){
        fin>>gx>>px;
        for(int j = 0; j <= g; j++)
            if(j - gx >= 0)
                DP[2][j] = max(DP[1][j], DP[1][j - gx] + px);
        for(int j = 0; j <= g; j++)
            DP[1][j] = DP[2][j];
    }
    fout<<DP[1][g];

}

int main(){

    rezolvare();
    return 0;

}