Sum of submatrix maxima

You have an $N \times N$ matrix $M$ of nonnegative integers. For every $K \times K$ submatrix of $M$, take the largest value inside it and write that value down. Submatrices may overlap, so the list holds $(N-K+1)^2$ values. One entry of $M$ can be the largest value of several submatrices, and then it appears in the list once for each of them. Compute the sum of the whole list.

Writing the matrix out would make the input huge, so you are given two arrays $A$ and $B$ of length $N$ together with two integers $C$ and $X$ instead. The value in row $i$ and column $j$ is

$M_{ij} = (A_i \times i + B_j \times j + C) \bmod X$

where $i$ and $j$ both run from 1 to $N$.

The first line holds the number of test cases $T$. The $T$ test cases follow.

The first line of each test case holds four integers $N$, $K$, $C$ and $X$, separated by spaces. The next two lines hold $N$ integers each: the first line is the array $A$ and the second line is the array $B$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the sum of the maximum values of all $K \times K$ submatrices.

• $1 \le T \le 100$
• $1 \le N \le 3000$
• $1 \le K \le N$
• $1 \le A_i, B_i \le 100000$
• $1 \le C \le 100000$
• $1 \le X \le 1000000007$

In the first test case of the example the matrix is

3

With $K = 1$ there is a single submatrix, so the answer is 3.

In the second test case the matrix is

9 3
1 6

With $K = 1$ each of the four entries is its own submatrix, so the answer is $9 + 3 + 1 + 6 = 19$.

In the third test case the matrix is

11 11 24
13 13 26
14 14 27

With $K = 2$ there are four submatrices whose maxima are 13, 26, 14 and 27, so the answer is 80.