Program p1;
uses math;
type p=record v,w:integer; end;
var a:array [1..5100] of p;
    b:array [0..10010,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:=1 to n-1 do begin
                        min:=a[i];
                        k:=i;
                        for j:=i+1 to n do if a[j].w<min.w then begin
                                                                min:=a[j];
                                                                k:=j;
                                                                end;
                        a[k]:=a[i];
                        a[i]:=min;
                        end;
     for i:=a[1].w to g do b[1,i]:=a[1].v;
     for i:=2 to n do for j:=a[i].w to g do b[i,j]:=max(b[i-1,j],b[i-1,j-a[i].w]+a[i].v);
     {for i:=1 to n do begin
                        writeln;
                        for j:=1 to g do write(b[i,j],' ');
                        end;   }
     writeln(fo,b[n,g]);
     close(fo);
end.