#include<stdio.h> 
#include <fstream>

using namespace std;

// A utility function that returns maximum of two integers 
int max(int a, int b) { return (a > b) ? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W 
int knapSack(int W, int wt[], int val[], int n)
{
	int i, w;
	int K[5000][10000];

	// Build table K[][] in bottom up manner 
	for (i = 0; i <= n; i++)
	{
		for (w = 0; w <= W; w++)
		{
			if (i == 0 || w == 0)
				K[i][w] = 0;
			else if (wt[i - 1] <= w)
				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
			else
				K[i][w] = K[i - 1][w];
		}
	}

	return K[n][W];
}

int main()
{
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	int val[10000];
	int wt[10000];
	int  W;
	int n;
	fin >> n >> W;
	for (int i = 0; i < n; ++i) {
		fin >> wt[i] >> val[i];
	}
	fout << knapSack(W, wt, val, n);

	return 0;
}