using namespace std;
#include <algorithm>
#include <cstring>
#define NMAX 5001
#define GMAX 10001
class Knapsack
{
    private:
		int a[GMAX];
    public:
		Knapsack()
		{
			memset(a,0,sizeof(a));
		}
		int solve(int n, int g, int w[], int v[])
		{
			int a[2][GMAX];
			int i,j;
			for(i=1;i<=n;i++)
			{
				for(j=0;j<=g;j++)
				{
					a[i%2][j]=a[(i-1)%2][j];
					if(j>=w[i])
						a[i%2][j]=max(a[i%2][j],a[(i-1)%2][j-w[i]]+v[i]);
				}
            }
            return a[n%2][g];
        }
		
		int solve2(int n,int g, int w[], int v[])
        {
            int i,j,best=0;
            for(i=1;i<=n;i++)
            {
                for(j=g-w[i];j;j--)
                //if(a[j])
                {
                    a[j+w[i]]=max(a[j]+v[i],a[j+w[i]]);
                    if(a[j+w[i]]>best) best=a[j+w[i]];
                }
				a[w[i]]=v[i];
            }
            return best;
        }
}K;

#include <fstream>
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int weights[NMAX],values[NMAX];
int main()
{
    int n,G;
    f>>n>>G;
    for(int i=1;i<=n;i++)
        f>>weights[i]>>values[i];
  
	g<<K.solve2(n,G,weights,values);

}