/*
URL_HERE
*/
/*

*/
#ifdef _WIN32
	#pragma warning(disable:4996)
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <unordered_map>
using namespace std;

FILE* _fin = stdin;
FILE* _fout = stdout;
#define PI 3.141592653589793238462643383279502884197169399375105820974
#define ten5p1 100001
#define ten6p1 1000001
#define ten8p1 100000001
#define ten9p1 1000000001
#define ll long long
#define ull unsigned long long
#define rep(var,n) for(int var=0;var<n;++var)
#define repi(n) rep(i,n)
#define repj(n) rep(j,n)
#define repi1(n) for(int i=1;i<n;++i)
#define _min(a,b) a<b?a:b
#define _max(a,b) a>b?a:b
#define zeroi(data,n) memset(data,0,sizeof(int)*n);
#define zeroll(data,n) memset(data,0,sizeof(long long)*n);
#define one(data,n) {for(int _ONEI=0;_ONEI<n;++_ONEI) data[_ONEI]=1;}
#define readc(var) fscanf(_fin,"%c",var)
int readi() { int var; fscanf(_fin, "%d", &var); return var; }
ll readll() { ll var; fscanf(_fin, "%lld", &var); return var; }
void repreadi(int* data, int n) { repi(n) data[i] = readi(); }
void repreadll(ll* data, int n) { repi(n) data[i] = readll(); }
int reads(char* str, int maxsize)
{
	for (;;){if (fgets(str, maxsize, _fin) == NULL) break;if (str[0] != '\n' && str[0] != '\r') break;}
	int slen = strlen(str);if (slen == 0) return 0;
	if (str[slen - 1] == '\n' || str[slen - 1] == '\r') str[--slen] = 0;
	return slen;
}

#define writec(var) fprintf(_fout,"%c",var)
#define writecsp(var) fprintf(_fout,"%c ",var)
#define writecln(var) fprintf(_fout,"%c\n",var)
#define writei(var) fprintf(_fout,"%d",var)
#define writeisp(var) fprintf(_fout,"%d ",var)
#define writellsp(var) fprintf(_fout,"%lld ",var)
#define writeiln(var) fprintf(_fout,"%d\n",var)
#define writellln(var) fprintf(_fout,"%lld\n",var)
#define writefln(var) fprintf(_fout,"%f\n",var)
#define writes(str) fprintf(_fout,"%s",str)
#define writesp() fprintf(_fout," ")
#define writeln() fprintf(_fout,"\n")
#define iseven(x) ((x&1)==0 ? 1:0)
#define RUN_LOCAL(testfilename) {_fin = fopen(testfilename, "r"); if(_fin==NULL) _fin=stdin;}
#define swap(type,a, b) {type t=a;a=b;b=t;}
#define swapxor(a,b) {a^=b;b^=a;a^=b;}
#define sort(data,n) std::sort(data,data+n)
#define mod(a,b) b==0 ? 0 : a==0 ? 0 :(a>0 ? a%b : b + a % b)
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }

void reversei(int* data, int n) { int k = n >> 1; repi(k) { int tmp = data[i]; data[i] = data[n - i - 1]; data[n - i - 1] = tmp; } }
int bsearch(int val, int* data, int n) { if (data[0] > val) return -1; if (data[n - 1] < val) return n; int l = 0; int r = n - 1; for (; l < r;) { int mid = (l + r + 1) >> 1; if (data[mid] <= val) l = mid; else r = mid - 1; }if (data[r] != val) ++r; return r; }

#define _Vec(type, name) \
struct name { type* data; int size; int n; };\
void init(name* t, int size) { t->data = (type*)malloc(sizeof(type) * size); t->size = size; t->n = 0; }\
void resize(name* t) { int ns = t->size * 1.2f; t->data = (type*)realloc(t->data, sizeof(type) * ns); t->size = ns; }\
void add(name* t, type val) { if (t->n >= t->size) resize(t); int k = t->n; t->data[k] = val; t->n = k + 1; }\
void free(name* t) { free(t->data);}
_Vec(int, Veci)
_Vec(long long, Vecll)
_Vec(char*, Vecs)

#define _ispal(type, name) int name(type* a, type* b, int n){repi(n){if (a[i] != b[n - i - 1]){return 0;}}return 1;}
_ispal(int, ispali)
_ispal(char, ispalc)

#define _Pair(type, name) struct name{type x, y;}; \
int cmp_##name(const void* _a, const void* _b){name* a = (name*)_a;name* b = (name*)_b;if (a->x == b->x){if (a->y < b->y) return -1;else return 1;}if (a->x < b->x) return -1;else return 1;}\
void sort_##name(name* d, int n){qsort(d, n, sizeof(name), cmp_##name);}
	_Pair(int, Pairi)

	int cmp_Str(const void* _a, const void* _b) { char* a = *((char**)_a); char* b = *((char**)_b); return strcmp(a, b); }
void sort_Str(char** str, int n) { qsort(str, n, sizeof(char*), cmp_Str); }


//------------

int main()
{
	RUN_LOCAL("atcoder_DP_D.txt");
	int n = readi();
	int w = readi();
	static int weight[100];
	static int value[100];
	repi(n)
	{
		weight[i] = readi();
		value[i] = readi();
	}
	static ll dp[2][ten5p1];
	memset(dp, 0, sizeof(ll) * 2 * ten5p1);

	dp[0][weight[0]] = value[0];
	ll best = dp[0][weight[0]];
	repi1(n)
	{
		repj(w) dp[1][j] = dp[0][j];
		dp[1][weight[i]] = _max(dp[1][weight[i]], value[i]);
		repj(w)
		{
			if (j + weight[i] > w) break;
			if (dp[0][j] != 0)
			{
				dp[1][j + weight[i]] = _max(dp[1][j + weight[i]], dp[0][j] + value[i]);

				best = _max(dp[1][j + weight[i]], best);
			}
		}

		repj(w) dp[0][j] = dp[1][j];
	}

	writellln(best);

	//repi(n)
	//{
	//	repj(w + 1) writeisp(dp[i][j]);
	//	writeln();
	//}

	return 0;
}

Measured memory_bytes: 1664