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

procedure citire;
var i:integer;
begin
assign(f,'energii.in'); reset(f);
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;
close(f);
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[j];
    a[j]:=a[i];
    a[i]:=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;

function min(a,b:longint):longint;
begin
if a<b then min:=a
       else min:=b;
end;

procedure det;
var i,j:integer;
begin
for i:=1 to min(ct,10000000) 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
citire;
qsort(1,n);
det;
end.