program problema_rucsacului;
var i,j,k,N,G:integer; L1,L2:array[0..10005] of longint;
W,P:array[1..5005] of longint; fin,fout:text; s:string;
bufin:array[0..100000] 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;
For i:=1 to N do
 begin
 L2[j]:=L1[j];
 For j:=W[i] to G do
  begin

  If L2[j]<L1[j-W[i]]+P[i] then
   L2[j]:=L1[j-W[i]]+P[i];
  end;
 For j:=0 to G do L1[j]:=L2[j];
 end;

Assign(fout,'rucsac.out'); Rewrite(fout);
Write(fout,L2[G]);
Close(fout);
end.