CF1676D.X-Sum

Timur's grandfather gifted him a chessboard to practice his chess skills. This chessboard is a grid $a$ with $n$ rows and $m$ columns with each cell having a non-negative integer written on it.

Timur's challenge is to place a bishop on the board such that the sum of all cells attacked by the bishop is maximal. The bishop attacks in all directions diagonally, and there is no limit to the distance which the bishop can attack. Note that the cell on which the bishop is placed is also considered attacked. Help him find the maximal sum he can get.

蒂穆尔的祖父送给他一个棋盘来练习国际象棋技巧。这个棋盘是一个 $n$ 行 $m$ 列的网格 $a$，每个格子中写有一个非负整数。

蒂穆尔的挑战是：在棋盘上放置一枚主教（Bishop），使得被该主教攻击到的所有格子上的数字之和最大。主教沿所有对角线方向攻击，且攻击距离没有限制。注意：主教所占据的格子本身也被视为被攻击。请帮助他找出所能获得的最大和。

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains the integers $n$ and $m$ ($1 \le n \le 200$, $1 \leq m \leq 200$).

The following $n$ lines contain $m$ integers each, the $j$-th element of the $i$-th line $a_{ij}$ is the number written in the $j$-th cell of the $i$-th row $(0\leq a_{ij} \leq 10^6)$

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $4\cdot10^4$.

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 200$，$1 \leq m \leq 200$）。

接下来的 $n$ 行每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个元素 $a_{ij}$ 表示第 $i$ 行第 $j$ 列格子中所写的数字（$0\leq a_{ij} \leq 10^6$）。

保证所有测试用例中 $n\cdot m$ 的总和不超过 $4\cdot10^4$。

For each test case output a single integer, the maximum sum over all possible placements of the bishop.

对于每个测试用例，输出一个整数，即主教所有可能放置位置中所能获得的最大和。

For the first test case here the best sum is achieved by the bishop being in this position:

对于第一个测试用例，主教位于以下位置时可得到最优的和：