#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[Nmax+1][Gmax+1];

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

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;


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