比赛 20100913 评测结果 AAAAAAAAAA
题目名称 越狱 最终得分 100
用户昵称 苏轼 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-09-13 21:35:46
显示代码纯文本
program prisonbreak(input,output);

var
  i,j,n,l,p,t:longint;
  oil:array[0..10000,1..2]of longint;
  dym:array[0..10000]of longint;

function max(a,b:longint):longint;
  begin
    if a>b then
      exit(a)
    else
      exit(b);
  end;

procedure swap(i,j:longint);
  var
    t1,t2:longint;
  begin
    t1:=oil[i,1];
    t2:=oil[i,2];

    oil[i]:=oil[j];
    oil[j,1]:=t1;
    oil[j,2]:=t2;
  end;

procedure sort(l,r: longint);
  var
    i,j,x,y: longint;
  begin
    i:=l;
    j:=r;
    x:=oil[(l+r) div 2,1];

    repeat
      while oil[i,1]<x do
        inc(i);

      while x<oil[j,1] do
        dec(j);

      if not(i>j) then
      begin
        swap(i,j);

        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');
  reset(input);

  assign(output,'prisonbreak.out');
  rewrite(output);

  readln(n);

  for i:=1 to n do
    readln(oil[i,1],oil[i,2]);

  readln(l,p);

  for i:=1 to n do
    oil[i,1]:=l-oil[i,1];

  sort(1,n);

  dym[0]:=p;
  for i:=1 to n do
    for j:=i downto 1 do
      if dym[j-1]>=oil[i,1] then
        dym[j]:=max(dym[j-1]+oil[i,2],dym[j]);

  for i:=0 to n do
    if dym[i]>=l then
    begin
      writeln(i);
      n:=-1;
      break;
    end;

  if n>-1 then
    writeln(-1);

  close(input);
  close(output);
end.