#include <iostream>
#include <fstream>
using namespace std;

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

const int MAX_N = 5005;
const int MAX_G = 10005;

int N, G;
int d[2][MAX_G];
int w[MAX_N];
int v[MAX_N];

inline int f(int i);

int main()
{
    fin >> N >> G;
    for (int i = 1; i <= N; i += 1) {
        fin >> w[i] >> v[i];
    }

    for (int i = 1; i <= N; i += 1) {
        for (int j = 1; j <= G; j += 1) {
            d[f(i)][j] = max(d[f(i)][j - 1], d[f(i - 1)][j]);
            if (j - w[i] >= 0) {
                d[f(i)][j] = max(d[f(i)][j], d[f(i - 1)][j - w[i]] + v[i]);
            }
        }
    }

    fout << d[f(N)][G];

    return 0;
}

inline int f(int i) {
    return i & 1;
}