Maximum Sum Subgrid

You are given several test cases. In each test case, a grid of integers is provided with dimensions (R \times C). Your task is to find the subgrid (i.e. contiguous rectangular region) with the maximum possible sum. More formally, given a grid (A) with (R) rows and (C) columns, you must find

[ S = \max_{1 \leq i \leq j \leq R,; 1 \leq k \leq l \leq C} \sum_{p=i}^{j} \sum_{q=k}^{l} A_{p,q} ]

where (A_{p,q}) is the element in the (p)th row and (q)th column. It is guaranteed that each test case has at least one element.

This problem can be solved efficiently using a 2D extension of Kadane's algorithm.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. Each test case starts with a line containing two integers (R) and (C), the number of rows and columns of the grid respectively. This is followed by (R) lines, each containing (C) space-separated integers representing the grid elements.

outputFormat

For each test case, output a single integer in a separate line --- the maximum sum achievable by any contiguous subgrid within the given grid. The output should be written to standard output (stdout).## sample

2
3 3
1 2 3
4 5 6
7 8 9
2 4
1 2 3 4
5 6 7 8

45
36