#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, g;
    cin >> n >> g;

    vector<pair<int, int>> v;
    vector<vector<int>> dp(n + 1, vector<int>(g + 1, 0));

    for (int i = 0; i < n; i++)
    {
        int w, p;
        cin >> w >> p;
        v.push_back({w, p});
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= g; j++)
        {
            if (j >= v[i - 1].first)
                dp[i][j] = max(dp[i - 1][j - v[i - 1].first] + v[i - 1].second, dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }

    cout << dp[n][g] << endl;
}