NOI199 九十九棋盘分割

---

[NOI1999]棋盘分割

题目描述：

对一个８*８的棋盘实施如下分割方式：首先从原棋盘中切割出一个矩形区域，使得剩余的部分同样保持为矩形形状；随后，从剩余的两个矩形区域中任选其一继续执行相同的操作。通过(n-1)次这样的切割过程，最终将得到共计n块矩形棋盘。需要注意的是，每一次切割均需严格沿棋盘格子的边界进行。

棋盘上的每个格子都对应一个数值，整个矩形棋盘的总分等于所有格子数值的总和。现在需要根据上述规则将棋盘分割为n块矩形区域，并使得各矩形区域总分的平方和达到最小值。

请编写程序，针对给定的棋盘和n，计算出平方和的最小可能值。

输入格式：

第1行包含一个整数n(1 < n < 15)。

第2行至第9行每行由8个非负整数构成，每个数均小于100，表示棋盘上对应位置的数值。每行中的相邻数字之间用空格隔开。

输出格式：

仅输出一个数值，即所求的平方和。

输入样例#1：

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