Description

Partition an $8 \times 8$ chessboard as follows: cut off a rectangular piece from the original board such that the remaining part is also a rectangle, then continue partitioning the remaining part in the same way. After cutting $(n-1)$ times, together with the final remaining rectangle, there are a total of $n$ rectangular pieces. (Each cut can only be made along the edges of the grid cells.)

Each cell on the original board has a score. The total score of a rectangular piece is the sum of the scores of all cells it contains. Now you need to partition the board into $n$ rectangular pieces according to the rule above, and minimize the standard deviation of the total scores of all rectangular pieces.

The standard deviation is

$$\sigma = \sqrt{ \frac{ \sum_{i=1}^n (x_i - \bar x)^2 } { n }}$$

where the average is

$$\bar x = \frac{\sum_{i=1}^n x_i}{n}$$

and $x_i$ is the score of the $i$-th rectangular piece.

Given the board and $n$, compute the minimum possible value of $\sigma$.

Input Format

The first line contains an integer $n$ ($1 < n < 15$).

Lines 2 to 9 each contain $8$ non-negative integers less than $100$, representing the scores of the corresponding cells on the board. Adjacent numbers in each line are separated by one space.

Output Format

Output only one number, $\sigma$, rounded to three digits after the decimal point.

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

1.633

Hint

Translated by ChatGPT 5