type rucsac=record
               w,p:longint;
               end;
tablou=array [1..5010]of rucsac;
var a:tablou;
    i,j,k,m,n,weight:longint;
    rez,aux:array [-1..10010]of int64;
    f,g:text;
begin
assign(f,'rucsac.in');
assign(g,'rucsac.out');
reset(f);
rewrite(g);
read(f,n,weight);
for i:=1 to n do
 read(f,a[i].w,a[i].p);
for i:=1 to n do
   begin
   for j:=a[i].w to weight do
       if (rez[j]>a[i].p+rez[j-a[i].w])then aux[j]:=rez[j]
        else aux[j]:=a[i].p+rez[j-a[i].w];
   for j:=1 to weight do
    rez[j]:=aux[j];
   end;
write(g,rez[weight]);
close(f);
close(g);
end.