Program rucsac_dinamic;
var fi,fo: text;
    cistig:array[0..2] of array[0..10000] of integer;
    g,cost,d:array[0..10000] of longint;
    m,n,i,j,w,r,aux : longint;

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

begin
    assign(fi,'rucsac.in'); reset(fi); readln(fi,n,w);
    assign(fo,'rucsac.out'); rewrite(fo);

    for i:=1 to n do readln(fi,g[i],cost[i]);

    for i:=1 to 2 do
       for j:=1 to w do cistig[i,j]:=0;

    for i:=1 to n do  begin
                      m:=2;
       for j:=1 to w do if g[i]<=j then cistig[m,j]:=max(cistig[m-1,j],cistig[m-1,j-g[i]]+cost[i])
                                   else cistig[m,j]:=cistig[m-1,j];

                      for r:=1 to w do begin
                                          aux:=cistig[2,r];
                                        if i<>n then   cistig[2,r]:=0;
                                          cistig[1,r]:=aux;
                                          end;
                      end;

    write(fo,cistig[2,w]);
    close(fi); close(fo);
end.