#include <fstream>

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

void PD(int n,int W,int v[],int w[],int val[])
{
    int i,j;
    for(i=0;i<=W;i++)
        val[i]=0;
    for(i=1;i<=n;i++)
    {
        for(j=W;j>=1;j--)
        {
            if(j>=w[i]&&val[j]<v[i]+val[j-w[i]])
            {
                    val[j]=v[i]+val[j-w[i]];
            }
        }
    }
}

//obiectele sunt numerotate de la 1, de aceea am pus -1 pe prima pozitie in vector in fisierul de input
int v[5005],w[5005],val[10005];
int main()
{
    int i,n,W;
    fin>>n>>W;
    for(i=1;i<=n;i++)
        fin>>w[i]>>v[i];
    PD(n,W,v,w,val);

    //Determinarea si afisarea solutiei
    int solmax=0;
    for(i=0;i<=W;i++)
       if(val[i]>solmax)
          solmax=val[i];
    fout<<solmax;
    return 0;
}