#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int MOD=123457;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n,G,W[5005],P[5005],Optim[10005],rasp=0;

int main()
{
f>>n>>G;
for(int i=1;i<=n;i++)
  f>>W[i]>>P[i];
Optim[0]=0;
for(int i=1;i<=n;i++)
 {
  for(int j=G-W[i];j>=0;j--)
    {
     Optim[j+W[i]]=max(Optim[j+W[i]],Optim[j]+P[i]);
     rasp=max(rasp,Optim[j+W[i]]);
    }
 }
g<<rasp;
}