#include <bits/stdc++.h>

using namespace std;

int n, g;
int w[5005], p[5005];
int dp[10005];
int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> g;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> p[i];
    }

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

    cout << dp[g];
    return 0;
}