#include <bits/stdc++.h>
#define pp pair< int, int >
#define g first
#define p second

using namespace std;

const int mxn = 5000 + 10;
const int mxg = 10 * 1000 + 10;

pp obiecte[ mxn ];
int pret[ mxg ];
int solutie = 0;

int main(){
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n, g;
    cin>> n >> g;
    for(int i = 0; i < n; i++){
        cin>> obiecte[ i ].g >> obiecte[ i ].p;
    }

    for(int i = 0; i < n; i++){
        int x = obiecte[ i ].g;
        int y = obiecte[ i ].p;
        for(int j = g - x, nx, ny; j >= 0; j--){
            nx = j + x;
            ny = pret[ j ] + y;
            if(pret[ nx ] < ny){
                pret[ nx ] = ny;
                solutie = max(solutie, ny);
            }
        }
    }

    cout<< solutie;
 	return 0;
}