#include <bits/stdc++.h>

using namespace std;

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

int DP[2][10005];
int n,G;

int main()
{
    int i,j,W,P,l=1;
    fin>>n>>G;
    for(i = 1; i <= n; i++){
        fin>>W>>P;
        for(j = 1; j < W; j++){
            DP[l][j] = DP[1-l][j];
        }
        for(j = W; j <= G; j++){
            DP[l][j] = max( DP[1-l][j], DP[1-l][j-W]+P );
        }
        l = 1-l;
    }
    fout<<DP[l][G]<<'\n';
    return 0;
}