// problema rucsac

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

#define NMax 5000
#define GMax 10000
#define iter for (int i = 1; i <= N; ++i)

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

int N, G, val[NMax + 3], w[NMax + 3];
int DP[2][GMax + 3];

void input() {
    fin >> N >> G;
    iter fin >> w[i] >> val[i];
}

void solve() {
    iter {
        for (int g = 1; g < w[i]; ++g) DP[1][g] = DP[0][g];
        for (int g = w[i]; g <= G; ++g)
            DP[1][g] = max(DP[0][g], DP[0][g - w[i]] + val[i]);
        for (int g = 1; g <= G; ++g)
            DP[0][g] = DP[1][g];
    }
    fout << DP[0][G];
}

int main() {
    input();
    solve();
}