#include<fstream>
#include<algorithm>
using namespace std;
const int MAXN = 5010;
const int MAXG = 10010;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N,G,Pmax;
int W[MAXN],P[MAXN];
int D[2][MAXG];
int main(){
    fin>>N>>G;
    for(int i=1;i<=N;++i)
        fin>>W[i]>>P[i];
    int l=0;
    for(int i=1;i<=N;++i,l=1-l)
    for(int cw=0;cw<=G;++cw){
        D[1-l][cw] = D[l][cw];
        if(W[i]<=cw)
            D[1-l][cw] = max(D[1-l][cw],D[l][cw-W[i]]+P[i]);
    }
    Pmax = D[l][G];
    fout<<Pmax;
    return 0;
}