var a:array[0..5000,0..10000] of int64;
    d,v:array[1..5000] of integer;
    c,n,i,j:integer;
    f,g:text;

begin
 assign(f,'rucsac.in');reset(f);
 assign(g,'rucsac.out');rewrite(g);
 readln(f,n,c);
 for i:=1 to n do
  readln(f,d[i],v[i]);
 for i:=0 to n do
  a[i,0]:=0;
 for j:=0 to c do
  a[0,j]:=0;
 for i:=1 to n do
  for j:=1 to c do
   if d[i]>j then a[i,j]:=a[i-1,j]
             else if a[i-1,j]>a[i-1,j-d[i]]+v[i] then a[i,j]:=a[i-1,j]
                                                 else a[i,j]:=a[i-1,j-d[i]]+v[i];
 write(g,a[n,c]);
 close(f);
 close(g);
end.