Program Rucsac1;
 uses crt;
var a: array[0..5020,0..10020] of word;
    m,c:array[1..5020] of word;
    n,i,j,g,s,k: word;
    fi,fo: text;
begin clrscr;
      assign(fi,'rucsac.in');
      assign(fo,'rucsac.out');
      reset(fi);
      rewrite(fo);

      read(fi,n);
      readln(fi,g);

      i:=0;
      while not(eof(fi)) do begin
                          inc(i);
                          read(fi,m[i]);
                          readln(fi,c[i]);
                       end;
      close(fi);

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

      for k:=1 to n do
          for s:=1 to g do begin
                     if s>=m[k] then begin
                                       if a[k-1,s-m[k]]+c[k] > a[k-1,s] then a[k,s]:=a[k-1, s-m[k]]+c[k]
                                                                       else a[k,s]:=a[k-1,s];
                                     end
                                else a[k,s]:=a[k-1,s];
                           end;


      writeln(fo,a[n,g]);
      close(fo);
end.