#include <fstream>
#define nmax 10001

using namespace std;

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

int n,G,P;
struct obiect
{
    int g;
    int c;
};

obiect a[nmax];
int c[nmax][nmax];

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

int maxim(int a,int b)
{
    if(a>b) return a;
    if(b>a) return b;
}

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]=maxim(c[i-1][j],a[i].c+c[i-1][j-a[i].g]);
}

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

int main()
{
    citire();
    dinamica();
    solutie();
    return 0;
}