#include <iostream>
#include <fstream>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

int N, G;
int dp[3][10005];
pair<int, int> v[5010];

int main()
{
    in >> N >> G;

    for(int i = 1; i <= N; i++)
        in >> v[i].second >> v[i].first;

    for(int i = v[1].second; i <= G; i++)
        dp[1][i] = v[1].first;

    //cout << 1 << ' ' << v[1].first << ' ' << v[1].second << '\n';

    //for(int i = 0; i <= G; i++)
    //    cout << dp[1][i] << ' ';

   //cout << '\n';

    for(int i = 2; i <= N; i++)
    {
        int current = (i % 2);
        int prev = 1 - current;

        int val = v[i].first;
        int w = v[i].second;

        //cout << i << ' ' << val << ' ' << w << '\n';

        for(int j = 0; j <= G; j++)
        {
            if(j - w < 0)
                dp[current][j] = dp[prev][j];
            else
                dp[current][j] = max(dp[prev][j], dp[prev][j - w] + val);

            //cout << dp[current][j] << ' ';
        }

        //cout << '\n';
    }

    out << max(dp[0][G], dp[1][G]) << '\n';

    return 0;
}