var m:array[0..10000,0..10000] of integer;
    v,w:array[1..5000] of integer;
    i,j,k,n,b:integer;
    f,g:text;
begin
assign(f,'rucsac.in');reset(f);
assign(g,'rucsac.out');rewrite(g);
readln(f,n,b);
for i:=1 to n do
  readln(f,w[i],v[i]);

for i:=1 to b do
  m[0,i]:=0;

for i:=1 to n do
  for j:=0 to b do
    if j>=w[i] then
        if m[i-1,j]>m[i-1,j-w[i]]+v[i] then m[i,j]:=m[i-1,j]
          else m[i,j]:=m[i-1,j-w[i]]+v[i]
        else m[i,j]:=m[i-1,j];

writeln(g,m[n,b]);


close(f);close(g);
end.