E. Data Miner
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tổ chức Global Data Science Collective (GDSC) vừa phát hiện ra một ma trận dữ liệu có $$$n$$$ hàng và $$$m$$$ cột. Biết rằng ô dữ liệu ở hàng thứ $$$i$$$ từ trên xuống và cột $$$j$$$ từ bên trái sang ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) có giá trị $$$a_{ij}$$$.

Sau khi nghiên cứu kỹ lưỡng, tổ chức cần chọn ra hai vùng không phủ nhau có diện tích $$$k \times k$$$ để tiến hành đào dữ liệu. Bạn hãy giúp tổ chức tìm ra hai vùng có tổng giá trị lớn nhất.

Input

Dòng đầu tiên gồm một số nguyên dương $$$t$$$ ($$$1 \le t \le 500$$$) $$$-$$$ số testcases.

Dòng đầu tiên ở mỗi testcase gồm ba số nguyên dương $$$n$$$, $$$m$$$ và $$$k$$$ ($$$2 \le n, m \le 10^3$$$, $$$1 \le k \le \lfloor\frac{\mathrm{min}(n, m)}{2}\rfloor$$$) $$$-$$$ số hàng, số cột và độ dài cạnh của vùng cần tìm.

$$$n$$$ dòng tiếp theo ở mỗi testcase gồm $$$m$$$ số nguyên dương $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$0 \le a_{ij} \le 10^9$$$) $$$-$$$ giá trị của mỗi ô dữ liệu.

Dữ liệu vào bảo đảm tổng $$$n$$$ không vượt quá $$$10^3$$$ và tổng $$$m$$$ không vượt quá $$$10^3$$$.

Output

Với mỗi test case, trên một dòng, in ra tổng giá trị lớn nhất thu được từ hai vùng đã chọn.

Example
Input
2
4 4 2
5 2 1 6
4 3 2 5
1 2 5 3
6 9 2 1
2 2 1
1 1
1 1
Output
33
2
Note

Sử dụng ($$$x_1, y_1, x_2, y_2$$$) đại diện cho một vùng (diện tích $$$k \times k$$$) với ($$$x_1, y_1$$$) đại diện cho tọa độ của ô trái trên, và ($$$x_2, y_2$$$) đại diện cho tọa độ của ô phải dưới.

Ở ví dụ thứ nhất, hai vùng ($$$3, 1, 4, 2$$$) và ($$$2, 3, 3, 4$$$) đã được chọn với tổng các ô nằm trên chúng là $$$33$$$.

Ở ví dụ thứ hai, bất kì vùng nào cũng cho giá trị là $$$1$$$, ta chọn hai trong số chúng từ đó có đáp án là $$$2$$$.