#include <bits/stdc++.h>

#define maxn 5001
#define maxg 10001

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

int n,gm,w[maxn],p[maxn];
int optim[maxg];
int main()
{
    f>>n>>gm;
    for (int i=1;i<=n;i++)
         f>>w[i]>>p[i];
    optim[0]=0;
    int sol=0;
    for (int i=1;i<=n;i++)
         for (int j=gm-w[i];j>=0;j--)
            {
              if(optim[j+w[i]]<optim[j]+p[i])
                {
                  optim[j+w[i]]=optim[j]+p[i];
                  if (optim[j+w[i]]>sol)
                      sol=optim[j+w[i]];
                }
            }
    g<<sol;
    return 0;
}