import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container, std.format;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

/*

ナップサック問題

xs[i][w]: i個目より前までで、重さw以下とした場合の価値の最大値

xs[0][w] = 0
xs[i][w] = (w - ws[i] >= 0)?
		xs[i - 1][w - ws[i]] + vs[i] : xs[i - 1][w]

*/

void main(){
	long n = read.to!long;
	long npw = read.to!long;
	
	long[] ws, vs;
	foreach(i; 0 .. n){
		ws ~= read.to!long;
		vs ~= read.to!long;
	}
	
	long[][] xs = [[]];
	foreach(w; 0 .. npw + 1) xs[0] ~= 0;
	
	foreach(i; 0 .. n){
		long[] q = [];
		foreach(w; 0 .. npw + 1){
			q ~= max(
					((w - ws[i] >= 0) ? xs[$ - 1][w - ws[i]] + vs[i] : 0),
					xs[$ - 1][w]
				);
			debug writeln("q:", q, " w:", w, " i:", i);
		}
		xs ~= q;
	}
	
	xs[n][npw].writeln;
}
