#include <bits/stdc++.h>

using namespace std;

const int nmax = 5001;
const int gmax = 10001;

int n, g;
int wei[nmax];
int val[nmax];
int dp[gmax];

int main() {
    freopen("carici.in", "r", stdin);

    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    scanf("%d%d", &n, &g);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &wei[i], &val[i]);
    }

    int solution = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = g - wei[i]; j >= 0; j--) {
            dp[j + wei[i]] = max(dp[j + wei[i]], dp[j] + val[i]);
            solution = max(solution, dp[j + wei[i]]);
        }
    }

    cout << solution << "\n";

    return 0;
}