12064번 - gMatrix (Small) 다국어

You have a square N by N matrix M of nonnegative integers. We would like to make a list of the maximum values in every sub-matrix of size K by K within M, and then find the sum of those values together. (Note that the same entry of M 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 A and B of length N, and two integers C and X. Then the entry M_ij (for the ith row and jth column of the matrix) equals (A_i*i+B_j*j + C) mod X, where i and j are in the range [1, N].

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

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

• 1 ≤ T ≤ 100.
• 1 ≤ A_i, B_i ≤ 100000.
• 1 ≤ C ≤ 100000.
• 1 ≤ X ≤ 1000000007.
• 1 ≤ K ≤ N. 
• 1 ≤ N ≤ 50.

In the first test case, the matrix is:

3

So the sum of maximum values is 3. In the second test case, the matrix is:

9 3
1 6

So the sum of maximum values is 19. In the third test case, the matrix is:

11 11 24
13 13 26
14 14 27