#include <bits/stdc++.h>
using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int Gmax = 10000;
const int Nmax = 5000;

int d[2][Gmax+1];
/// pair<int, int> prv[Nmax+1][Gmax+1];

int n, g;
int v[Nmax+1];
int w[Nmax+1];

int main()
{
    in>> n >> g;

    for(int i=1; i<=n; i++) {
        in>> w[i] >> v[i];
    }

    for(int i=0; i<=g; i++) d[0][i] = -1;
    d[0][0] = 0;

    int p = 0;

    for(int i=1; i<=n; i++) {
        /// adaug obiectul "i"
        p = !p;
        for(int j=0; j<=g; j++) d[p][j] = -1;
        for(int j=0; j<=g; j++) {
            if(d[!p][j] != -1 && j + w[i] <= g) {
                if(d[!p][j] + v[i] > d[p][j + w[i]]) {
                    d[p][j + w[i]] = d[!p][j] + v[i];
                }
            }
        }
        for(int j=0; j<=g; j++) {
            d[p][j] = max( d[p][j], d[!p][j] );
        }
    }

    int maxim=0;
    for(int i=1; i<=g; i++)
        maxim = max(maxim,d[p][i]);
    out<< maxim <<'\n';

    return 0;
}