#include <fstream>

using namespace std;

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

struct obiect
{int g;
int c;
};

obiect a[5001];
int n,G;
int C[5001][10001];

void Citire()
{int i,j;
fin>>n>>G;
for(i=1;i<=n;i++)
    fin>>a[i].g>>a[i].c;
}

void Dinamica()
{int i,j;/*
for(i=0;i<=G;i++)
    C[0][i]=0;
for(i=0;i<=n;i++)
    C[j][0]=0;*/
for(i=1;i<=n;i++)
    for(j=1;j<=G;j++)
        if(a[i].g>j) C[i][j]=C[i-1][j];
        else C[i][j]=max(C[i-1][j],a[i].c+C[i-1][j-a[i].g]);
fout<<C[n][G];
}

int main()
{
Citire();
Dinamica();
    return 0;
}