Optimal Partitioning of an 8x8 Chessboard

Given an (8\times 8) chessboard in which each cell contains an integer score, your task is to cut the board into (n) rectangular pieces using the following procedure:

1. Initially, the entire board is considered as a single rectangle.
2. A cut is performed by removing a rectangular piece from the border of an existing rectangle (i.e. the cut must follow the grid lines and the removed piece must be contiguous and adjacent to one of the edges) such that the remaining part is also a rectangle.
3. In each step, exactly one of the current rectangular pieces is chosen to be cut further. After (n-1) cuts, there will be (n) rectangular pieces in total.

The score for a rectangle is defined as the sum of all the scores in its cells. If the (n) pieces have sums (S_1, S_2, \dots, S_n), the objective is to minimize the quantity [ \sum_{i=1}^{n} S_i^2, ] i.e. the sum of the squares of the scores of the pieces.

Write a program that, given the chessboard and (n), computes the minimum possible sum of squares achievable.

inputFormat

The input consists of 9 lines. The first line contains a positive integer (n) ((1 \le n \le 64)), the number of pieces. The next 8 lines each contain 8 space-separated integers, representing the scores of the chessboard cells. The j-th number in the i-th line is the score at row (i) and column (j).

outputFormat

Output a single integer: the minimum possible sum of squares of the scores of the final (n) rectangular pieces.

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

4096