Description

Partition an $8\times 8$ chessboard as follows: cut off a rectangular subboard from the original chessboard so that the remaining part is also a rectangle; then pick either of the two remaining parts and continue to partition it in the same way. After doing this $(n-1)$ times, together with the final remaining rectangle, there are $n$ rectangular boards. (Each cut may only follow the edges of the grid cells.)

Each cell on the original chessboard has a score. The total score of a rectangular board is the sum of the scores of its cells. Partition the chessboard into $n$ rectangles according to the rule above so that the sum of squares of the rectangles’ total scores is minimized.

Given the chessboard and $n$, write a program to compute the minimum possible sum of squares.

Input Format

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

Lines two through nine each contain $8$ non-negative integers less than $100$, representing the scores of the corresponding cells on the chessboard. Adjacent numbers in the same line are separated by a single space.

Output Format

Output a single number: the minimum sum of squares.

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

1460

Hint

Translated by ChatGPT 5