Story

You work in a beverage factory. In this factory, a large quantity of drinking water is prepared, and carbonated beverages, the final products, are made by adding syrup and carbon dioxide. By varying the amounts of syrup and carbon dioxide added, multiple variants of carbonated beverages can be produced. Furthermore, it is possible to add syrup or carbon dioxide to already made beverages to make other variants.

Given multiple combinations of desired sweetness and carbonation levels of the beverages you want to make, find an efficient way to produce them.

Problem Statement

The sweetness and carbonation level of beverages are represented by non-negative integers. A beverage with sweetness x and carbonation level y is denoted by (x, y).

Initially you only have beverage (0, 0). Below we write S for the set of beverages already made. Initially S = \{(0, 0)\}.

You can repeat the following operation to make multiple beverages.

• Choose an already made beverage (x, y) \in S.
• Choose integers x', y' such that x' \ge x and y' \ge y.
• Divide beverage (x, y) into two containers, and keep one of them. Make a new beverage (x', y') by adding the appropriate amount of syrup and carbon dioxide to the other. Add (x', y') to S.
  • Notice that (x, y) will not be removed from S.
• This operation costs (x' - x) + (y' - y).

Given N beverages (A_1, B_1), \dots, (A_N, B_N) in the input, you can perform the above operation up to 5N times. Find a sequence of operations that makes all of the specified beverages (that is, a sequence of operations such that (A_i, B_i) \in S holds for all i \in \{1, 2, \dots, N\} after all operations) with the total cost as small as possible. It is allowed to make beverages not present in the input during the process.

Scoring

Let C be the total cost, and L = \max\{A_1, B_1, A_2, B_2, \dots, A_N, B_N\}. Then the score is given by \mathrm{round}\left(10^6 \times \frac{NL}{1 + C}\right).

There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Sample Input 1

4
0 6
2 5
3 2
4 0

Sample Output 1

6
0 0 2 0
0 0 0 6
2 0 4 0
2 0 2 2
2 2 3 2
2 2 2 5

This is an example for illustrative purposes, and does not satisfy the constraints on input.

The beverages you want to make are (0, 6), (2, 5), (3, 2), (4, 0). Let S be the set of beverages already made, as in the problem statement.

• The first operation makes (2, 0) from (0, 0), and costs 2.
  • After this operation, S = \{(0, 0), (2, 0)\}.
• The second operation makes (0, 6) from (0, 0), and costs 6.
  • After this operation, S = \{(0, 0), (2, 0), (0, 6)\}.
• The third operation makes (4, 0) from (2, 0), and costs 2.
  • After this operation, S = \{(0, 0), (2, 0), (0, 6), (4, 0)\}.
• The fourth operation makes (2, 2) from (2, 0), and costs 2.
  • After this operation, S = \{(0, 0), (2, 0), (0, 6), (4, 0), (2, 2)\}.
• The fifth operation makes (3, 2) from (2, 2), and costs 1.
  • After this operation, S = \{(0, 0), (2, 0), (0, 6), (4, 0), (2, 2), (3, 2)\}.
• The sixth operation makes (2, 5) from (2, 2), and costs 3.
  • After this operation, S = \{(0, 0), (2, 0), (0, 6), (4, 0), (2, 2), (3, 2), (2, 5)\}.

Finally, S contains all of (0, 6), (2, 5), (3, 2), (4, 0), so this output will be judged as AC.

The total cost is 16. Since C = 16, L = 6, N = 4, the score is \mathrm{round}\left(10^6 \times \frac{6 \times 4}{1 + 16}\right) = 1411765.