#include <iostream>
#include <fstream>
#include <algorithm>
#define nMax 5010
#define gMax 10010
using namespace std;

int M[nMax][gMax];
int value[nMax],weight[nMax];
int n,w;
ifstream in("rucsac.in");
ofstream out("rucsac.out");

void read()
{
    in>>n>>w;
    for(int i=1;i<=n;i++)
    {
        in>>weight[i]>>value[i];
    }
}

int resolve(int i,int j)
{
    if(i==0)
    {
        return 0;
    }
    if(M[i][j]!=0)
    {
        return M[i][j];
    }
    if(j<weight[i])
    {
        return M[i-1][j]=resolve(i-1,j);
    }
    return M[i][j]=max(resolve(i-1,j),resolve(i-1,j-weight[i])+value[i]);
}
void write()
{
    out<<M[n][w];
}
int main()
{
    read();
    resolve(n,w);
    write();
}