#include <iostream>
#include <fstream>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int gmax = 10001;
const int nmax = 5001;
struct obiect
{
    int gr,pr;
};
obiect ob[nmax];
int dp[3][gmax];

int main()
{
    int n,G;
    in>>n>>G;
    for(int i = 1; i <= n; i++)
        in>>ob[i].gr>>ob[i].pr;
    for(int i = 1; i <= n ; i++)
    {
        int linc = i % 2;
        int linant = 1 - i % 2;
        for(int j = 0; j <= G; j++)
            if(j - ob[i].gr >= 0)
                dp[linc][j] = max(dp[linant][j - ob[i].gr] + ob[i].pr, dp[linant][j]);
            else
                dp[linc][j] = dp[linant][j];
    }
    int maxig = 0;
    for(int i = G; i >= 1; i--)
        maxig = max(maxig, dp[n % 2][i]);
    out<<maxig;
    return 0;
}