#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int N, G, W[5005], P[5005];
int profit[10005];
bool posibil[10005];
int Gmax=0, Pmax=0;
int main()
{
    f>> N >> G;
    for(int i=1;i<=N;i++)
    {
        f>>W[i]>>P[i];
    }
    posibil[0]=true;
    for(int i=1;i<=N;i++)
    {
        for(int j=Gmax;j>=0;j--)
        {
            if(posibil[j])
            {
                if(j+W[i]<=G)
                {
                    if(profit[j]+P[i]>profit[j+W[i]])
                    {
                        profit[j+W[i]]=profit[j]+P[i];
                        Pmax=max(Pmax, profit[j+W[i]]);
                    }

                    posibil[j+W[i]]=true;
                }
            }
        }
        Gmax=min(Gmax+W[i], G);
    }
    g<<Pmax;
    return 0;
}