Program rucsac_arena;
type maxim=0..10000;
var f1,f2:text;
    cost,g:array[0..5000] of maxim;
    cistig:array[0..5000,0..10000] of maxim;
    w,j,i,n:maxim;

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

begin
    assign(f1,'rucsac.in'); reset(f1); readln(f1,n,w);
    for i:=1 to n do read(f1,g[i],cost[i]);
    assign(f2,'rucsac.out'); rewrite(f2);
    for i:=0 to n do for j:=0 to w do cistig[i,j]:=0;
    for i:=1 to n do
        for j:=1 to w do
                         if g[i]<=j then cistig[i,j]:=max(cistig[i-1,j],cistig[i-1,j-g[i]] + cost[i])
                                    else cistig[i,j]:=cistig[i-1,j];
   writeln(f2,cistig[n,w]);
   close(f1); close(f2);
end.