#include <bits/stdc++.h>

#define g first
#define p second

using namespace std;

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


pair <int, int> obiecte[ mxn ];

int dp[ mxg ];

int n, g;

int dpRec(int obj, int cost, int greutate){
    if(greutate + obiecte[ obj ].g > g){
        return cost;
    }

    greutate += obiecte[ obj ].g;
    cost += obiecte[ obj ].p;

    int sol = cost;

    for(int i = obj + 1; i <= n; i++){
        sol = max(sol, dpRec(i, cost, greutate));
    }
    return sol;
}

int dpIter(){


    //dp[ i ][ j ] = costul cel mai mare adaugand obiectul i cu o greutate j

    int sol = 0;

    for(int i = 1; i <= n; i++){
        int x = obiecte[ i ].g;
        int y = obiecte[ i ].p;
        for(int j = g - x; j >= 0; j--){
            int ng = j + x;
            int np = dp[ j ] + y;
            if(np > dp[ ng ]){
                dp[ ng ] = np;
                sol = max(sol, np);
            }
        }
    }

    return sol;
}

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

    cout<< dpIter();

    return 0;
}