program problema_rucsacului;
var i,j,k,N,G:integer; L:array[0..55,0..10005] of longint;
W,P:array[1..5005] of longint; fin,fout:text; s:string;
bufin:array[0..50000] of char;
begin
Assign(fin,'rucsac.in'); Reset(fin);
settextbuf(fin,bufin);
Readln(fin,N,G);
For i:=1 to N do
 begin
 //Readln(fin,W[i],P[i]);
 Readln(fin,s);
 k:=1; j:=0;
 While ord(s[k])<>ord(' ') do
  begin
  j:=10*j+ord(s[k])-ord('0');
  inc(k);
  end;
 W[i]:=j; j:=0; inc(k);
 While k<=length(s) do
  begin
  j:=10*j+ord(s[k])-ord('0');
  inc(k);
  end;
 P[i]:=j;
 end;

 k:=1;
For i:=1 to N do
 begin
 If k = 50 then
  begin
  For j:=0 to G do L[0,j]:=L[k,j];
  k:=1;
  end;

 L[k,j]:=L[k-1,j];
 For j:=W[i] to G do
  begin

  If L[k,j]<L[k-1,j-W[i]]+P[i] then
   L[k,j]:=L[k-1,j-W[i]]+P[i];
  Write(L[k,j],' ');
  end;

// For j:=1 to G do Write(L[k,j],' ');
 Writeln;

 inc(k);
 end;

Assign(fout,'rucsac.out'); Rewrite(fout);
Write(fout,L[k-1,G]);
Close(fout);
end.