부분행렬 최댓값의 합

음이 아닌 정수로 이루어진 $N \times N$ 행렬 $M$이 있다. $M$ 안에 들어 있는 모든 $K \times K$ 부분행렬마다 그 안의 최댓값을 하나씩 골라 목록을 만든 다음, 목록에 있는 값을 전부 더한 값을 구하려고 한다. 부분행렬끼리는 서로 겹칠 수 있으므로 목록의 길이는 $(N-K+1)^2$이다. 같은 칸이 여러 부분행렬에서 동시에 최댓값이 되면 그 값은 목록에 여러 번 들어간다.

행렬을 그대로 입력하면 크기가 너무 커지므로, 길이가 $N$인 배열 $A$와 $B$, 그리고 정수 $C$와 $X$가 대신 주어진다. $i$번째 행 $j$번째 열의 값 $M_{ij}$는 다음과 같이 정한다.

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

$i$와 $j$는 모두 1 이상 $N$ 이하이다.

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

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

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

• $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$

예제의 첫 번째 테스트 케이스에서 행렬은 다음과 같다.

3

$K = 1$이라 부분행렬이 하나뿐이므로 답은 3이다.

두 번째 테스트 케이스의 행렬은 다음과 같다.

9 3
1 6

$K = 1$이므로 네 칸이 각각 부분행렬이 되고, 답은 $9 + 3 + 1 + 6 = 19$이다.

세 번째 테스트 케이스의 행렬은 다음과 같다.

11 11 24
13 13 26
14 14 27

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