[Solution] X-Sum solution codeforces

X-Sum solution codeforces – 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.

[Solution] X-Sum solution codeforces

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.

Input

The first line of the input contains a single integer 𝑡t (1𝑡10001≤t≤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𝑛2001≤n≤2001𝑚2001≤m≤200).

The following 𝑛n lines contain 𝑚m integers each, the 𝑗j-th element of the 𝑖i-th line 𝑎𝑖𝑗aij is the number written in the 𝑗j-th cell of the 𝑖i-th row (0𝑎𝑖𝑗106)(0≤aij≤106)

It is guaranteed that the sum of 𝑛𝑚n⋅m over all test cases does not exceed 41044⋅104.

[Solution] X-Sum solution codeforces

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

Example
input

Copy
4
4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
2 1
1
0
3 3
1 1 1
1 1 1
1 1 1
3 3
0 1 1
1 0 1
1 1 0
output

Copy
20
1
5
3

[Solution] X-Sum solution codeforces

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

For Solution

Click here

Leave a Comment