Chessboard Partitioning Minimization

Given an 8 \( \times \) 8 chessboard where each cell has an integer score, you are to split the board according to the following rule: at each cut, remove a rectangular sub-board from the current rectangle such that the remaining part is also a rectangle. After \(n-1\) cuts, you will have \(n\) rectangular pieces. The score of a rectangle is the sum of the scores of its cells.

Let \(x_i\) denote the score of the \(i\)-th rectangle. The standard deviation \(\sigma\) is defined in \(\LaTeX\) format as follows:

\[ \sigma = \sqrt{\frac{\sum_{i=1}^{n} (x_i - \bar{x})^2}{n}}, \quad\text{where}\quad \bar{x} = \frac{\sum_{i=1}^{n} x_i}{n}. \]

Your task is to partition the chessboard into \(n\) rectangles using only cuts along the grid lines so that \(\sigma\) is minimized, and then output the minimum value of \(\sigma\) rounded to three decimal places.

inputFormat

The first line contains an integer \(n\) representing the number of rectangular pieces.

The next 8 lines each contain 8 integers. The \(j\)-th number in the \(i\)-th line denotes the score of the cell at row \(i\) and column \(j\) of the chessboard.

outputFormat

Output the minimum standard deviation \(\sigma\) rounded to three decimal places.

sample

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 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

0.000