P16513 [GKS 2015 #C] gMatrix

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 $\mathbf{A}$ and $\mathbf{B}$ of length $N$, and two integers $\mathbf{C}$ and $\mathbf{X}$. Then the entry $M_{ij}$ (for the $i$th row and $j$th column of the matrix) equals $(\mathbf{A}_i \times i + \mathbf{B}_j \times j + \mathbf{C}) \pmod{\mathbf{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 $\mathbf{A}$ and $\mathbf{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$.

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 ``` ### Limits $1 \le T \le 100$. $1 \le A_i, B_i \le 100000$. $1 \le C \le 100000$. $1 \le X \le 1000000007$. $1 \le K \le N$. **Small dataset (Test Set 1 - Visible)** $1 \le N \le 50$. **Large dataset (Test Set 2 - Hidden)** $1 \le N \le 3000$.