using namespace std;
#include <algorithm>
#include <cstring>
#define NMAX 5001
#define GMAX 10001
class Knapsack
{
    private:
        int a[2][GMAX];
    public:
		Knapsack()
		{
			memset(a[1],0,sizeof(a[1]));
		}
		int solve(int n, int g, int w[], int v[])
		{
			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];
        }
}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.solve(n,G,weights,values);

}