现有n块”多米诺骨牌”s1,s2,s3,...sn水平放成一排,每次骨牌si包含左右两个部分,每个部分赋予一个非负整数值,如下图所示为包含6块骨牌的序列.骨牌可做180度旋转,使得原来在左边的值变到右边,而原来右边的值移到左边,假设不论si如何旋转,L[i]总是存储si左边的值, R[i]总是存储si右边的值, W[i]用于存储si的状态:当L[i]<=R[i]时记为0,否则记为1,试采用分治法设计算法求:R[1]*L[2]+R[2]*L[3]+R[3]*L[4]+R[4]*L[5]+...++R[n-1]*L[n]的最大值,以及当取得最大值时每个骨牌的状态.
        5|8      4|2     9|6    7|7    3|9    11|10
         s1       s2        s3     s4       s5       s6

Program dom;
Type
  arr = Array[0..1000] of Integer;
Const
  infile = 'dom.in';
  outfile = 'dom.out';
Var
  c, f: arr;
  i, n, x, y, s1, s2, ans: Integer;
Procedure try1(i: Integer);
Begin
  If i = 0 Then Begin
    f[i]:= abs(s1 - s2);
    Exit;
  End;
  try1(i - 1);
  If f[i - 1] > abs(s1 - s2 + c[i]) Then Begin
    f[i]:= abs(s1 - s2 + c[i]);
    Inc(ans);
  End Else f[i]:= f[i - 1];
End;
Begin
  Assign(input, infile);
  Reset(input);
  Readln(n);
  s1:= 0;
  s2:= 0;
  For i:=1 to n do Begin
    Readln(x, y);
    Inc(s1, x);
    Inc(s2, y);
    c[i]:= 2 * (y - x);
  End;
  Close(input);
  ans:= 0;
  try1(n);
  Assign(output, outfile);
  Rewrite(output);
  Writeln(ans);
  Close(output);
End.