#include<bits/stdc++.h>
using namespace std;
int N, M, Pmax;//M-masa N -Nr de 
bool u;
int G[5000], P[5000];//G Greutate 
int D[2][1000 ];
   
int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    fin >> N >> M;
    for(int i = 1; i <= N; ++i)
    fin >> G[i] >> P[i];
    for(int i = 1; i <= N; ++i){
    for(int m = 0; m <= M; ++m){
    D[u][m] = D[!u][m];
    if(G[i] <= m)
    D[u][m] = max(D[u][m], D[!u][m - G[i]] + P[i]);            
    }
    u = !u;
    }
    u = !u;
    Pmax = D[u][M];
    fout << Pmax;
    return 0;
}