记录编号	47421	评测结果	AAAAAAAAAA
题目名称	多米诺骨牌	最终得分	100
用户昵称	天下第一的吃货殿下	是否通过	通过
代码语言	Pascal	运行时间	0.334 s
提交时间	2012-11-01 14:35:19	内存使用	38.41 MiB

var
 a,b,c,d,e,n:longint;
 q1,q2:array[1..1000] of longint;
 dp:array[0..1000,-5006..5006] of longint;
  function min(xx,yy:longint):longint;
        begin
           if  xx>yy then exit(yy)
             else exit(xx);
   end;
   begin
    assign(input,'dom.in');
     reset(input);
      assign(output,'dom.out');
       rewrite(output);
     readln(n);
      for a:=1 to n do
       read(q1[a],q2[a]);
      for a:=0 to n do
         for b:=-5006 to 5006 do
           dp[a,b]:=maxlongint-1;
           dp[0,0]:=0;
      for a:=1 to n do
       for b:=-a*5 to a*5 do
       dp[a,b]:=min(dp[a-1,b-q1[a]+q2[a]],dp[a-1,b+q1[a]-q2[a]]+1);
     for a:=0 to n*5 do
        begin
         if dp[n,a]<>maxlongint-1 then begin
            writeln(min(dp[n,a],dp[n,-a]));
            break;
         end;
     end;
    close(input);
     close(output);
  end.