#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int main(){
    short n, g, w[5001], p[5001], V[5001][10001], i, j;
    in>>n>>g;
    for(i=1; i<=n; i++){
        in>>w[i]>>p[i];
    }
    for(i=0; i<=n; i++){
        V[0][i]=0;
        V[i][0]=0;
    }
    for(i=1; i<=n; i++){
        for(j=1; j<=g; j++){
            if(j<w[i]){
                    V[i][j]=V[i-1][j];
            }else{
                if(V[i-1][j]>V[i-1][j-w[i]]+p[i]){
                    V[i][j]=V[i-1][j];
                }else{
                    V[i][j]=V[i-1][j-w[i]]+p[i];
                }
            }
        }
    }
    out<<V[n][g];
    return 0;
}