type tab=array[0..5010] of longint;
	 tab2=array[1..2,0..10010] of longint;
var a,b:text;
	i,mass,n,j,q,p,mmin: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;
mmin:=mass;
for i:=1 to n do
	begin
	if m[i]<mmin then mmin:=m[i];
	for j:=mmin to mass do
	begin
		q:=2; 
		p:=1;
		if i mod 2=0 then 
			begin 
			q:=1; p:=2; 
			end;
		if (j-m[i])>=0 then t[p,j]:=max(t[q,j],v[i]+t[q,j-m[i]]) else t[p,j]:=t[q,j] 
	end;
	end;

	
writeln(b,max(t[2,j],t[1,j]));

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