#include <iostream>
#include <fstream>
using namespace std;

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


int dp[2][10005];
int v[5005][2];


int main()
{
    int n, g;
    fin >> n >> g;


    for (int i = 1; i <= n; i++)
    {
        fin >> v[i][0] >> v[i][1];
    }

    int idx = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= g; j++)
        {
            if (j -  v[i][0] < 0)
            {
                dp[idx][j] = dp[1 - idx][j];
            }
            else
            {
                dp[idx][j] = max(dp[1 - idx][j -  v[i][0]] + v[i][1], dp[1 - idx][j]);
            }
        }
        idx = 1 - idx;
    }

    fout << dp[1 - idx][g] << '\n';
    return 0;
}