program rucsac;
function max(a,b:integer):integer;
begin
        if a>b then max:=a else max:=b;
end;
        var d:array [0..5000,0..10000] of integer;
            gp,pr:array [0..5000] of integer;
            gr,n,i,j:integer;
            fi,fo:text;
begin
        assign(fi,'rucsac.in');
        assign(fo,'rucsac.out');
        reset(fi);
        rewrite(fo);
        readln(fi,n,gr);
        for i:=1 to n do readln(fi,gp[i],pr[i]);
        for i:=0 to gr do d[0,i]:=0;
        for i:=1 to n do begin
                                 for j:=0 to gr do begin
                                                           if gp[i]<=j then d[i,j]:=max(d[i-1,j],d[i-1,j-gp[i]]+pr[i])
                                                                       else d[i,j]:=d[i-1,j];
                                                   end;
                         end;
        writeln;
        writeln(fo,d[n,gr]);
        close(fi);
        close(fo);
end.