Maximum Subgrid Sum

You are given an N × M grid of integers. Your task is to find the maximum sum of any subgrid of size P × Q within the grid. A subgrid is a contiguous block of the grid. It is guaranteed that P ≤ N and Q ≤ M.

To solve this problem efficiently, you are encouraged to use a prefix sum (or cumulative sum) technique to quickly calculate the sum of any subgrid in constant time.

Formally, if we denote the grid by \(a_{i,j}\), and define a prefix sum array \(S\) such that \[ S(i,j) = \sum_{x=1}^{i} \sum_{y=1}^{j} a_{x,y}, \] then the sum of a subgrid with top-left corner at \((i-P+1, j-Q+1)\) and bottom-right corner at \((i, j)\) is given by \[ S(i,j) - S(i-P,j) - S(i,j-Q) + S(i-P,j-Q). \] Your goal is to iterate over all possible subgrids of size \(P \times Q\) and output the maximum sum found.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N M P Q
row_1
row_2
...
row_N
... (repeated for each test case)

Here, the first line contains an integer \(T\), the number of test cases. For each test case:

• The first line contains four integers \(N\), \(M\), \(P\), \(Q\), where \(N\) and \(M\) denote the dimensions of the grid, and \(P\) and \(Q\) denote the dimensions of the subgrid.
• The next \(N\) lines each contain \(M\) integers separated by spaces, representing the grid.

outputFormat

For each test case, output a single line (to standard output) containing the maximum sum of any subgrid of size \(P \times Q\).

2
4 5 2 3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
3 3 2 2
-1 -2 -3
-4 -5 -6
-7 -8 -9

99
-12