#216548. [GKS 2015 #C] gMatrix

You have a square by matrix of nonnegative integers. We would like to make a list of the maximum values in every sub-matrix of size by within , and then find the sum of those values together. (Note that the same entry of might be the maximum value in more than one sub-matrix, in which case it will show up multiple times in the list.) Can you find that sum?

To simplify the input of the matrix, you are given two arrays and of length , and two integers and . Then the entry (for the th row and th column of the matrix) equals , where and are in the range .

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with one line with four integers, , , and . Then there are two lines with integers each, representing the arrays and .

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and is the sum of the maximum values in all sub-matrices of size by .

样例输入 1

3
1 1 1 5
1
1
2 1 5 11
1 2
3 4
3 2 3 109
6 4 3
2 1 5

样例输出 1

Case #1: 3
Case #2: 19
Case #3: 80

In the first test case, the matrix is:

3

So the sum of maximum values is .

In the second test case, the matrix is:

9 3
1 6

So the sum of maximum values is .

In the third test case, the matrix is:

11 11 24
13 13 26
14 14 27

Limits

.

.

.

.

.

Small dataset (Test Set 1 - Visible)

.

Large dataset (Test Set 2 - Hidden)

.