Program P1;
  var a:array[0..10010] of integer;
      b:array[0..10010] of integer;
      c:array[0..10010] of integer;
      i,n,g,x,m,j:integer;
      fi,fo:text;
begin
      assign(fi,'rucsac.in'); reset(fi);
      assign(fo,'rucsac.out'); rewrite(fo);
      read(fi,n);
      readln(fi,g);
      for i:=1 to n do begin
                       read(fi,a[i]);
                       readln(fi,c[i]);
                       end;
      b[0]:=1;
      m:=0;
      for i:=1 to n do begin
                         for j:=g downto a[i] do begin
                                                if b[j-a[i]]-c[i]>b[j] then b[j]:=b[j-a[i]]+c[j];
                                                if b[j]>m then m:=b[j];
                                                end;
                         end;
      write(fo,m);
      close(fo);
end.