#include <bits/stdc++.h>
using namespace std;

int dp[5005][10005], w[10005], p[10005];

int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n, g;
    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 = 0; j <= g; ++j)
        {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i])
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + p[i]);
        }

    cout << dp[n][g];

    return 0;
}