#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,gr,pd[2][10000],w[5000],c[5000];
void cit(){
    fin>>n>>gr;
    int i;
    for(i=1;i<=n;i++)
        fin>>w[i]>>c[i];
}
int main(){
    cit();
    int i,j;
    for(i=1;i<=n;i++)
        for(j=0;j<=gr;j++)
            if(j>=w[i])
                pd[i%2][j]=max(pd[(i-1)%2][j],pd[(i-1)%2][j-w[i]]+c[i]);
            else
                pd[i%2][j]=pd[(i-1)%2][j];
    fout<<pd[n%2][gr];
    return 0;}