PROB03 - Vùng bao lớn nhất

no tags 

English

Given a matrix of size M×N (1<= M, N <= 100). Each point in the matrix is a positive integer.

Given 2 numbers W and H (1 <= H <= M, 1 <= W <= N). With a rectangle at any point in the matrix of size H×W (H is vertical, W is horizontal).

Find the rectangle whose sum of even numbers is the largest and print that sum.

Input

The first line is the number of test cases of the problem (1 <= T <= 100)

With each test case

  • The first line is 4 numbers H, W, M, N.
  • Next is the matrix of size M×N.

Output

The result of each test case is printed on 1 line. With:

  • Start with the character "#", followed by the ordinal number of that test case, followed by a space (space), and finally the Result of that test case.

Example

Input:
1
3 2 5 6
26 63 38 56 76 49
92 55 9 90 13 21
53 39 1 52 21 74
82 66 27 86 79 31
2 13 57 63 34 72

Output:
#1 274

Vietnamese

Cho một ma trận kích thước M*N (1<= M, N <= 100). Mỗi điểm trong ma trận là một số nguyên dương.

Cho 2 số W và H (1<=H<=M, 1<=W<=N). Với một hình chữ nhật tại 1 điểm bất kỳ trong ma trận có kích thước H*W (H là chiều dọc, W là chiều ngang).

Hãy tìm ra hình chữ nhật có tổng các số chẵn là lớn nhất và in ra tổng đó.

Input

Dòng đầu tiên là số lượng test case của bài toán (1 <= T <= 100)

Với mối testcase

- Dòng đầu tiên là 4 số H, W, M, N

- Tiếp đến là ma trận kích thước M*N

Output

Kết quả mỗi testcase được in trên 1 dòng. Với:

Bắt đầu bằng ký tự "#", tiếp theo là số thứ tự của testcase đó, tiếp đến là 1 khoảng trắng (dấu cách), và cuối cùng là Kết quả của testcase đó.

Example

Input:
1
3 2 5 6
26 63 38 56 76 49
92 55 9 90 13 21
53 39 1 52 21 74
82 66 27 86 79 31
2 13 57 63 34 72
Output: #1 274


Added by:Đặng Xuân Bảo
Date:2020-02-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All