记录编号 18931 评测结果 AAAAAAAAAA
题目名称 越狱 最终得分 100
用户昵称 Gravatarreamb 是否通过 通过
代码语言 Pascal 运行时间 2.922 s
提交时间 2010-09-24 18:05:34 内存使用 0.23 MiB
显示代码纯文本
program yueyu13;

var

  a,w:array[1..10000]of longint;

  i,j,l,p,max,n,min:longint;

  f:array[0..10000] of longint;

procedure sort(l,r: longint);

var

  i,j,x,y: longint;

begin

  i:=l;

  j:=r;

  x:=a[(l+r) div 2];

  repeat

    while a[i]<x do

      inc(i);

    while x<a[j] do

      dec(j);

    if not(i>j) then

    begin

      y:=a[i];

      a[i]:=a[j];

      a[j]:=y;

      y:=w[i];

      w[i]:=w[j];

      w[j]:=y;

      inc(i);

      j:=j-1;

   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 (a[i],w[i]);

    readln (l,p);

    for i:=1 to n do

      a[i]:=l-a[i];

    sort(1,n);

    for j:=0 to n do

      f[j]:=-maxlongint;

    f[0]:=p;

    if p>=a[1] then

      f[1]:=f[0]+w[1];

    if p>=l then

      writeln (0)
    else

    begin

    min:=maxlongint;

    for i:=2 to n do

      for j:=i downto 1 do

      begin

        max:=-maxlongint;

        if f[j-1]>=a[i] then

          max:=f[j-1]+w[i];

        if f[j]>=a[i] then

          if f[j]>max then

            max:=f[j];

        f[j]:=max;

        if max>=l then

          if j<min then

            min:=j

      end;

    if min=maxlongint then

      writeln ('-1')

    else
      writeln (min)

    end;

  close (input);

  close (output)

end.