Program p1;
uses math;
type p=record v,w:integer; end;
var a:array [1..5100] of p;
    b:array [0..2,0..10010] of longint;
    n,g,i,j,k:longint;
    min:p;
    f,fo:text;
Begin
     assign(f,'rucsac.in');
     assign(fo,'rucsac.out');
     reset(f);
     rewrite(fo);
     readln(f,n,g);
     for i:=1 to n do readln(f,a[i].w,a[i].v);
     for i:=a[1].w to g do b[1,i]:=a[1].v;
     for i:=2 to n do begin
                        k:=1;
                        for j:=a[i].w to g do b[2,j]:=max(b[1,j],b[1,j-a[i].w]+a[i].v);
                        for j:=1 to g do b[1,j]:=b[2,j];
                        end;
     {for i:=1 to n do begin
                        writeln;
                        for j:=1 to g do write(b[i,j],' ');
                        end;   }
     writeln(fo,b[2,g]);
     close(fo);
end.