//Solutie  O(n*c)

#include <iostream>
#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,greutate,weight[10001],cost[10001],i,mat[10001][10001];

int rucsac(int n, int c)
{
    int rezultat,obiect1,obiect2;
    if(mat[n][c]!=0)
        return mat[n][c];
    else
    {
    if(n==0 || c==0)
        rezultat=0;
    else
        if(weight[n]>c)
            rezultat=rucsac(n-1,c);
        else
        {
            obiect1=rucsac(n-1,c);
            obiect2=cost[n]+rucsac(n-1,c-weight[n]);
            rezultat=max(obiect1,obiect2);
        }
        mat[n][c]=rezultat;
    return rezultat;
    }
}

int main()
{
    f>>n>>greutate;
    weight[0]=cost[0]=0;
    for(i=1;i<=n;i++)
        f>>weight[i]>>cost[i];
    g<<rucsac(n,greutate);

    return 0;
}