Program rucsac_dinamic;
type tudor=array[0..10000] of longint;
var fi,fo: text;
    cistig:array[0..2] of tudor;
    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-1 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];
                                          cistig[2,r]:=0;
                                          cistig[1,r]:=aux;
                                          end;
                      end;


       i:=n;               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];

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