#include <iostream>
#include <cstdio>

using namespace std;

int castig[5001][10001],alege[5001][10001],gr[10001],c[5001],i,j,n,g,obiect;

int main()
{
    FILE *fin=fopen("rucsac.in","r"),
        *fout=fopen("rucsac.out","w");
    fscanf(fin,"%d %d ",&n,&g);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d %d ",&gr[i],&c[i]);
    for(i=1;i<=n;i++)
        for(j=1;j<=g;j++)
        if(gr[i]<=j)
            if(c[i]+castig[i-1][j-gr[i]]>castig[i-1][j])
            {
                castig[i][j]=c[i]+castig[i-1][j-gr[i]];
                alege[i][j]=i;
            }
            else
            {
                castig[i][j]=castig[i-1][j];
                alege[i][j]=alege[i-1][j];
            }
        else
        {
            castig[i][j]=castig[i-1][j];
            alege[i][j]=alege[i-1][j];
        }
    i=n;
    j=g;
    fprintf(fout,"%d \n",castig[i][j]);
    return 0;
}