Program Rucsak;
    var buf1, buf2 : array[1..1 shl 17] of char;
        n, g, i, j : longint;
        w, p : array [1..10000] of longint;
        zer, un : integer;
        a : array [0..1, 0..10000] of longint;
        fi, fo : text;

function max(a,b:longint):longint;
 begin
 if a>=b then max:=a else max:=b;
 end;

procedure swap(var a,b:integer);
    var x : integer;
    begin x:=a;
          a:=b;
          b:=x;
    end;

begin
 settextbuf(fi,buf1);
 settextbuf(fo,buf2);
 zer:=0; un:=1;
 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 1 do
     for j:=0 to g do a[i,j]:=0;

 for i:=1 to n do begin
                  for j:=1 to g do if w[i]>j then a[un,j]:=a[zer,j]
                                             else a[un,j]:=max(a[zer,j-w[i]]+p[i],a[zer,j]);
                  swap(zer,un);
                  end;


 writeln(fo,max(a[zer,g],a[un,g]));


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