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{i=1 to T}[Xi * (V.Vi)]
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:</p>
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 10Output: 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
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 start α of the vector, then K numbers of the vector.
1 ≤ R, C, H≤ 100, 1 ≤ K ≤ 500, 0 ≤ T ≤ 500, 0 ≤ G ≤ 100 and -5 ≤ α ≤ 5. G is the range of values for vectors Vi.