#include <iostream>
#include <fstream>
#define NMAX 5005
#define GMAX 10005
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N,G;
int profitmax[5][GMAX],greutate[NMAX],profit[NMAX];

int main()
{
fin>>N>>G;
for(int i=1;i<=N;i++)fin>>greutate[i]>>profit[i];
    for(int i=1;i<=N;i++)
        for(int j=0;j<G;j++)
    {
        int row=i%2;
        int opusrow=1-row;
        profitmax[row][j]=max(profitmax[opusrow][j],profitmax[row][j-1]);
        if(j>=greutate[i])profitmax[row][j]=max(profitmax[row][j],profitmax[opusrow][j-greutate[i]]+profit[i]);
    }
    fout<<profitmax[N%2][G];

    return 0;
}