A B C D E F

E. 矢巨开彡

喜欢矩形，尤其是很像正方形的矩形。对于一个 的矩阵，她可以选择任意两行和任意两列来围出一个矩形。

将矩形水平两条边上的所有数（不含端点）求和得到 ，垂直两条边上所有数（不含端点）求和得到 。定义矩形的“长”为 ，“宽”为 。矩形的“长宽比” （可能是负数）越接近 越好（与 之差的绝对值越小越好）。为了避免除以 ，当 时，这种选择视作不合法，忽略该矩形。

请找到一个框住至少 个数的矩形，要求该矩形“长宽比”尽量接近 ，求矩形内框住的数字之和（不含边）。如果有多个矩形一样优，请给出最大的和，没有符合条件矩形时输出 。

输入的第一行一个整数 ，表示后续输入组数。 对于每组输入： 第一行为两个正整数 和 （），表示矩阵的大小。 接下来的 行每行有 个整数，表示这个矩阵，矩阵中均为int范围内的整数。

对于每组输入： 输出一行，表示最优矩形内部元素的和的最大值。

【样例输入】

1
4 3
-1 -2 -3
12 -2 -3
-3 -2 3
-1 -2 -3

【样例输出】

-2

说明：

对于所有可能的行列组合，我们计算每种情况下的“长”、“宽”及“长宽比”，并忽略“宽”为 的情况：

1. 选择第 行和第 行，以及第 列和第 列：

   • 上下边（水平）求和得到 ，所以 。
   • 左右边（垂直）求和得到 ，所以 。
   • 因此，“长”为 ，“宽”为 ，“长宽比”为 。矩形内元素之和为 。

2. 选择第 行和第 行，以及第 列和第 列：

   • 上下边求和得到 ，所以 。
   • 左右边求和得到 ，所以 。
   • 这种情况下，“长”为 ，“宽”为 ，“长宽比”同样为 。矩形内元素之和为 。

3. 选择第 行和第 行，以及第 列和第 列：

   • 上下边求和得到 ，所以 。
   • 左右边求和得到 ，所以 。
   • 在这种情况下，“长”为 ，“宽”为 ，“长宽比”为 。矩形内元素之和为 。

在这些选项中，第三种情况具有最接近 的“长宽比”值（即 ）。因此，最终的答案是 。

。在注意本题奇怪的计算过程的同时，也请注意时间限制。

顺带一提，这道题的名字读作： 矢 (shǐ) 巨 (jù) 开 (kāi) 彡 (shān)