#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;
    int w1,p1;cin >> w1 >> p1;
    for (int j = w1; j <= g; j++)
        dp[1][j] = p1;

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

       // cout << '\n';
    }

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