program energii;
type tip=record
     e,c:integer;
     end;
const inf=maxint;
var f,g:text;
    a:array[1..5000] of tip;
    c:array[0..10000] of integer;
    n,gg,cost,ct:longint;

procedure citire;
var i:integer;
begin
readln(f,n);
readln(f,gg);
ct:=0;
for i:=1 to n do begin
  readln(f,a[i].e,a[i].c);
  ct:=ct+a[i].c;
  end;
end;

function part(l,r:integer):integer;
var i,j,p,pp:integer; aux:tip;
begin
pp:=a[r].c;
p:=a[r].e;
j:=l-1;
for i:=l to r do
  if (a[i].e<p) or ((a[i].e=p) and (a[i].c<pp)) then begin
    inc(j);
    aux:=a[i];
    a[i]:=a[j];
    a[j]:=aux;
    end;
part:=j;
end;

procedure qsort(l,r:integer);
var poz:integer;
begin
poz:=part(l,r);
if l<poz-1 then qsort(l,poz-1);
if r>poz+1 then qsort(poz+1,r);
end;

procedure det;
var i,j:integer;
begin
for i:=1 to ct do c[i]:=inf;
c[0]:=0;
for i:=1 to n do
  for j:=ct-a[i].c downto 0 do
    if (c[j]<>inf) and (c[j]+a[i].c<c[j+a[i].e]) then c[j+a[i].e]:=c[j]+a[i].c;
i:=gg;
while c[i]=inf do inc(i);
writeln(g,c[i]);
end;

begin
assign(f,'energii.in');
assign(g,'energii.out');
reset(f);
rewrite(g);
citire;
qsort(1,n);
det;
close(f);
close(g);
end.