#include <iostream>
#include <fstream>
#include <algorithm>
#define gMax 10010
#define nMax 5010
using namespace std;
int n,w;
int v[gMax],value[nMax],weight[nMax];
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];
    }
}

void resolve()
{
    for(int i=n;i>=1;i--)
    {
        for(int j=w;j-weight[i]>=0;j--)
        {
            v[j]=max(v[j],v[j-weight[i]]+value[i]);
        }
    }
}

void write()
{
    out<<v[n];
}
int main()
{
    read();
    resolve();
    write();
}