#include<bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int main() {
    int N, G;
    in >> N >> G;
    int v[N + 1], g[N + 1];
    for(int i = 1; i <= N; ++i) {
        in >> g[i] >> v[i];
    }
    int dp[N + 1][G + 1];
    for(int i = 0; i <= N; ++i) {
        for(int j = 0; j <= G; ++j) {
            dp[i][j] = -1;
            // nu exista
        }
    }
    dp[0][0] = 0;
    for(int i = 1; i <= N; ++i) {
        for(int currentG = 0; currentG <= G; currentG++) {
            if(currentG - g[i] >= 0 && dp[i - 1][currentG - g[i]] != -1) {
                dp[i][currentG] = max(dp[i][currentG], dp[i - 1][currentG - g[i]] + v[i]);
            }
            dp[i][currentG] = max(dp[i][currentG], dp[i - 1][currentG]);
        }
    }
    int answer = 0;
    for(int i = 0; i <= G; ++i) {
        answer = max(answer, dp[N][i]);
    }
    out << answer << '\n';
}