#include <fstream>
#define nmax 5001

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

int n,G, C[nmax][nmax];
struct obiect
{
    int g,c;
};

obiect a[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<=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];
}

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

int main()
{
    citire();
    dinamica();
    solutie();
    fin.close();
    fout.close();
    return 0;
}