#include <iostream>

using namespace std;

int dp[5005][10006];

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int n, g;
    cin >> n >> g;

    for (int i = 1; i <= n; i++)
    {
        int wi, pi;
        cin >> wi >> pi;
        for (int j = 0; j <= g; j++)
        {
            if (j - wi >= 0)
                dp[i][j] = max(dp[i-1][j], pi+dp[i-1][j-wi]);
            else
                dp[i][j] = dp[i-1][j];
            //cout << dp[i][j] << " ";
        }

       // cout << '\n';
    }

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