FISHES - Finding Fishes

Marlin engaged Dory, last April and they decided to marry in next November. Unfortunately, Dory is not like normal girls who their dowry is money, rings or furniture! She has many pictures of fishes and she wants a program that draws boxes around the fishes in the images. Time is passing and Marlin’s program just process the image and output some data that could be used to find the correct locations of these boxes. Please help him to save his marriage dream.

Marlin outputs for every image:

  • 2 integers H and K.
  • A 2D matrix M of integer values from 1 to K.
  • T integer vectors Vi, each of length K. Each vector is coupled with an integer value Xi.

A Score Evaluator function is used to calculate the score of any box in the image, such that the higher box score, the more confidence in the box to tightly contain a fish. Hence, Marlin targets the box with the highest score that contains a fish.

Given 4 corners of box B, the function works as following:

  • Construct vector V that has the frequencies of the values in M corresponding to B.
  • Calculate the score as: Score = H + $\sum_{1}^{T}[X_i * (V.V_i)]$, where (a.b) means the dot product.

Input

The first line of input contains an integer S that represents the number of test cases, then S test cases follow. Each test case start with a line of 5 numbers R C H K T, where R and C are number of rows and columns for the matrix. K, T and H are as described in the problem. R lines follow each with C numbers corresponding to the matrix. Then T lines for the vectors follow each line starts with X of that vector, then K numbers of the vector.

1 ≤ R, C, H ≤ 100, 1 ≤ K ≤ 500, 0 ≤ T ≤ 500, 0 ≤ G ≤ 100 and -5 ≤ X ≤ 5. G is the range of values for vectors Vi.

Output

For each test case, output on a single line “Case #K:” where K is the number of the test case, followed by a single integer which is the score of the box with highest to have a fish.

Example

Input:
1
3 4 7 3 2
1 1 2 2
1 2 2 3
2 3 1 3
-3 1 1 2
4 7 2 10

Output:
Case #1:
234

Explanation

Let's evaluate the first 2x2 box which is:

1 1
1 2

1 occurred 3 times, 2 occurred 1 time and 3 occurred 0 times. Then the frequencies vector is [3 1 0] and its function evaluation is:

7 + (- 3 * ([3 1 0]. [1 1 2]) + 4 * ([3 1 0].[7 2 10]) ) = 7 + (-12 + 92) = 87


Added by:Mostafa Saad Ibrahim
Date:2012-11-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:11th Egyptian Collegiate Programming Contest

hide comments
2012-11-10 20:21:02 :D
I seems it's one of those rare instances of input encoding issues (2 byte minus sings maybe). I don't recommend using buffered input for fast reading.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.