gMatrix (Small)

크기가 $N \times N$인 정사각 행렬 $M$이 있다. $M$의 원소는 모두 음이 아닌 정수이다. $M$ 안에 들어 있는 모든 $K \times K$ 부분 행렬마다 그 안의 최댓값을 하나씩 구한 다음, 구한 값을 전부 더한 결과를 구하려고 한다. 여기서 부분 행렬은 연속한 $K$개의 행과 연속한 $K$개의 열로 이루어진다. $M$의 같은 칸이 여러 부분 행렬에서 동시에 최댓값이 될 수 있는데, 그런 칸은 최댓값이 된 횟수만큼 중복해서 더한다.

행렬을 그대로 입력받는 대신 길이가 $N$인 두 배열 $A$와 $B$, 그리고 두 정수 $C$와 $X$가 주어진다. $i$번째 행, $j$번째 열의 원소는 $M_{ij} = (A_i \times i + B_j \times j + C) \bmod X$이다. 이때 $i$와 $j$는 모두 $1$ 이상 $N$ 이하이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 네 정수 $N$, $K$, $C$, $X$가 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $A$의 원소 $N$개가, 셋째 줄에는 배열 $B$의 원소 $N$개가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄에 Case #x: y 형식으로 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 모든 $K \times K$ 부분 행렬의 최댓값을 더한 값이다.

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

첫 번째 테스트 데이터의 세 번째 테스트 케이스는 $N = 3$, $K = 2$, $C = 3$, $X = 109$, $A = (6, 4, 3)$, $B = (2, 1, 5)$이므로 행렬은 다음과 같다.

11 11 24
13 13 26
14 14 27

$2 \times 2$ 부분 행렬은 네 개이고 각각의 최댓값은 $13$, $26$, $14$, $27$이므로 답은 $80$이다.