#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[G + 1];
    for(int i = 0; i <= G; ++i) {
        dp[i] = 0;
    }
    dp[0] = 0;
    for(int i = 1; i <= N; ++i) {
        for(int predG = G - g[i]; predG >= 0; predG--) {
            if(dp[predG] != -1) dp[predG + g[i]] = max(dp[predG + g[i]], dp[predG] + v[i]);
        }
    }
    int answer = 0;
    for(int i = 0; i <= G; ++i) {
        answer = max(answer, dp[i]);
    }
    out << answer << '\n';
}