using namespace std;
#include <algorithm>
#include <cstring>
#define NMAX 5001
#define GMAX 10001
class Knapsack
{
    private:
        int a[NMAX][GMAX];
    public:
		Knapsack()
		{
			memset(a[0],0,sizeof(a[0]));
		}
		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][j]=a[i-1][j];
					if(j>=w[i])
						a[i][j]=max(a[i][j],a[i-1][j-w[i]]+v[i]);
				}
            }
            return a[n][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);

}