#include <iostream>
#include <algorithm>
#include <cstring>

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 dp[2][GMAX]; // dp[pos][cap] = considerand doar obiectele [pos ... N] si avand la dispozitie un rucsac de capacite cap, care e profitul maxim
                    // pe care il putem obtine
/*bool vis[NMAX][GMAX];

//Memoizare
//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 dp[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 = dp[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';

    bool h = 0;
    for (int pos = N; pos; -- pos, h ^= 1) {
        memset(dp[h], 0, sizeof(dp[h]));

        for (int cap = 0; cap <= G; ++ cap) {
            //NU luam obiectul pos
            dp[h][cap] = dp[h ^ 1][cap];

            //LUAM obiectul pos
            if (w[pos] <= cap)
                dp[h][cap] = max(dp[h][cap], p[pos] + dp[h ^ 1][cap - w[pos]]);
        }
    }

    cout << dp[h ^ 1][G] << '\n';
    return 0;
}