#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;

    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;

        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);
        }
    }

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

    return 0;
}