type tab=array[0..5010] of longint;
	 tab2=array[0..5010,0..10010] of longint;
var a,b:text;
	i,mass,n,j:longint;
	m,v:tab;
	t:tab2;
	
function max(x,y:longint):longint;
begin
	if x>y then max:=x else max:=y;
end;	
	
begin
assign(a,'rucsac.in'); reset(a);
assign(b,'rucsac.out'); rewrite(b);
readln(a,n,mass);
for i:=1 to n do
	begin
	readln(a,m[i],v[i]);
	end;
	
for i:=1 to n do
	for j:=1 to mass do
		if (j-m[i])>-1 then t[i,j]:=max(t[i-1,j],v[i]+t[i-1,j-m[i]]) else t[i,j]:=t[i-1,j];

writeln(b,t[i,j]);

close(a);
close(b);
end.