#include <iostream>

using namespace std;

int dp[3][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%2][j] = max(dp[(i-1)%2][j], pi+dp[(i-1)%2][j-wi]);
            else
                dp[i%2][j] = dp[(i-1)%2][j];
            //cout << dp[i][j] << " ";
        }

       // cout << '\n';
    }

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