var a,c:array[1..100] of integer;
    b:array[0..100,0..1000] of integer;
    N,G,i,j:word;
    fi,fo:text;

function max(i:integer;j:integer):integer;
 var result:integer;
   begin
if i>j then result:=i else result:=j;
max:=result;
   end;


begin
assign(fi,'rucsac.in');reset(fi);
assign(fo,'rucsac.out');rewrite(fo);	

readln(N,G);

for i:=1 to n do readln(a[i],c[i]);
close(fi);

for j:=0 to g do b[0,j]:=0;
for i:=0 to n do b[i,0]:=0;

for i:=1 to n do for j:=1 to g do begin if j-a[i]<=0 then b[i,j]:=max(b[i-1,j],c[i]) else
                                                b[i,j]:= max(b[i-1,j],b[i-1,j-a[i]]+c[i]);
                                  end;


for i:=1 to n do begin for j:=1 to g do write(b[i,j]:5);
                       writeln;
                   end;

write(fo,b[n,g]);
close(fo);
end.