POLSKI SPOJ

Twoim zadaniem jest znalezienie w macierzy liczb (o rozmiarze a × b) kwadratu o boku c, którego suma elementów będzie możliwie największa.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 100) określająca liczbę zestawów danych.

W pierwszej linii każdego zestawu danych znajdują się dwie liczby a, b (2 ≤ a, b ≤ 1000) określające rozmiar macierzy. W kolejnych a liniach znajduje się po b liczb z zakresu od -1000 do 1000, są to elementy przeszukiwanej macierzy. W ostatniej linii znajduje się jedna liczba całkowita c (1 ≤ c ≤ Min(a, b)) określająca długość boku szukanego kwadratu.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać sumę elementów znalezionego kwadratu.

Przykład

Wejście:

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

Wyjście:

0
33