#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int main() {
    int N, G;
    fin >> N >> G;
    int W[N], V[N];
    int DP[2][G+1];
    for (int i = 0; i <= G; ++i) {
        DP[0][i] = 0;
        DP[1][i] = 0;
    }
    for (int i = 0; i < N; ++i) {
        fin >> W[i] >> V[i];
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= G; ++j) {
            DP[i%2][j] = max(DP[(i-1)%2][j], j >= W[i-1] ? DP[(i-1)%2][j - W[i-1]] + V[i-1] : 0);
        }
    }
    fout << DP[N%2][G] << endl;
    return 0;
}