记录编号	18653	评测结果	AAAAAAAAAA
题目名称	216.越狱	最终得分	100
用户昵称	Achilles	是否通过	通过
代码语言	Pascal	运行时间	1.789 s
提交时间	2010-09-17 09:42:32	内存使用	0.24 MiB

program prisonbreak;
var
  n,m,i,j,ans:longint;
  sz:array[0..11000,1..2]of longint;
  min:array[0..11000]of longint;
procedure sort(l,r:longint);
var
  i,j,mid,p:longint;
begin
  i:=l;
  j:=r;
  mid:=sz[(l+r) div 2,1];
  repeat
    while sz[i,1]<mid do inc(i);
    while mid<sz[j,1] do dec(j);
    if i<=j then
    begin
      p:=sz[i,1];
      sz[i,1]:=sz[j,1];
      sz[j,1]:=p;
      p:=sz[i,2];
      sz[i,2]:=sz[j,2];
      sz[j,2]:=p;
      inc(i);
      dec(j);
    end;
  until i >j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;
begin
  assign(input,'prisonbreak.in');
  assign(output,'prisonbreak.out');
  reset(input);
  rewrite(output);
  readln(n);
  n:=n;
  for i:=1 to n+1 do
    readln(sz[i,1],sz[i,2]);
  m:=sz[n+1,1];
  min[0]:=sz[n+1,2];
  sort(1,n);
  ans:=2000000000;
  for i:=n downto 1 do
  begin
    for j:=n-i+1 downto 1 do
    begin
      if min[j-1]>=m-sz[i,1] then
        if min[j-1]+sz[i,2]>min[j] then min[j]:=min[j-1]+sz[i,2];
    end;
  end;
  for i:=0 to n do
    if min[i]>=m then
      if i<ans then ans:=i;
  if ans=2000000000 then writeln(-1) else writeln(ans);
  close(input);
  close(Output);
end.