#include <iostream>
#include <algorithm>

using namespace std;

const int NMAX = 5000 + 5;
const int GMAX = 10000 + 5;
const int INF = NMAX * GMAX + 5;

int N, G;
int w[NMAX];
int p[NMAX];

void read() {
    cin >> N >> G;
    for (int i = 1; i <= N; ++ i)
        cin >> w[i] >> p[i];
}

int rasp[NMAX][GMAX];
bool vis[NMAX][GMAX];

//Stari sunt N * G
int backtr(int pos, int cap) { //pos e intre 1 si N si cap e intre 0 si G
    if (cap < 0)
        return -INF;
    if (pos == N + 1)
        return 0;

    if (vis[pos][cap])
        return rasp[pos][cap];
    vis[pos][cap] = true;

    //Suntem la obiecul pos (despre 1 ... pos - 1 stim ca deja s-a decis ce se face cu ele
    int &bestProf = rasp[pos][cap];

    bestProf = 0;

    if (pos == N + 1)
        return 0;
    //NU luam obiectul pos
    bestProf = max(bestProf, backtr(pos + 1, cap));

    //LUAM obiectul pos
    bestProf = max(bestProf, p[pos] + backtr(pos + 1, cap - w[pos]));

    //Returnam
    return bestProf;
}

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    read();

    cout << backtr(1, G) << '\n';
    return 0;
}