#include <fstream>
#include <cmath>
#define nmax 5001
using namespace std;

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

struct obiect
{int g;
 int c;};

obiect a[nmax];
int n,G,c[nmax][nmax];

void Citire()
{int i;
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(j=0;j<=n;j++)
    c[j][0]=0;
for(i=1;i<=n;i++)
    for(j=1;j<=n;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];
}

void solutie()
{int x,y;
x=n;
y=G;
while(c[x][y]!=0)
    if(c[x][y]!=c[x-1][y])
        {fout<<x<<" ";
        y=y-a[x].g;
        y--;
        }
    else x--;
}


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