Program Rucsak;
    var buf1, buf2 : array[1..1 shl 17] of char;
        n, g, i, j : longint;
        w, p : array [1..10000] of longint;
        a : array [0..5000, 0..10000] of longint;
        fi, fo : text;
function max(a,b:longint):longint;
 begin
 if a>=b then max:=a else max:=b;
 end;

begin
 settextbuf(fi,buf1);
 settextbuf(fo,buf2);

 assign(fi,'rucsac.in'); reset(fi);
 assign(fo,'rucsac.out'); rewrite(fo);
 readln(fi,n,g);
 for i:=1 to n do readln(fi,w[i],p[i]);
 for i:=0 to n do
     for j:=0 to g do a[i,j]:=0;

 for i:=1 to n do
     for j:=1 to g do if w[i]>j then a[i,j]:=a[i-1,j]
                                 else a[i,j]:=max(a[i-1,j-w[i]]+p[i],a[i-1,j]);
 writeln(fo,a[n,g]);


 close(fi);
 close(fo);
end.