gMatrix

음이 아닌 정수로 이루어진 N × N 정사각 행렬 M이 있다. M 안에 있는 크기 K × K의 모든 부분 행렬에서 최댓값을 구해 목록을 만들고, 그 값들을 모두 더한 합을 구하려 한다. (M의 동일한 원소가 둘 이상의 부분 행렬에서 최댓값일 수도 있으며, 이 경우 목록에 여러 번 나타난다는 점에 유의하라.) 이 합을 구할 수 있는가?

행렬의 입력을 단순화하기 위해 길이가 N인 두 배열 A와 B, 그리고 두 정수 C와 X가 주어진다. 이때 행렬의 i번째 행과 j번째 열에 있는 원소 $M_{ij}$는 ($A_{i}$*i+$B_{j}$*j + C) mod X와 같으며, i와 j는 $[1, N]$ 범위에 있다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $A_{i}$, $B_{i}$ ≤ 100000. 1 ≤ C ≤ 100000. 1 ≤ X ≤ 1000000007. 1 ≤ K ≤ N.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. 1 ≤ N ≤ 50.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 90초. 1 ≤ N ≤ 3000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 네 정수 N, K, C, X가 있는 한 줄로 시작한다. 그다음에는 각각 N개의 정수로 이루어져 배열 A와 B를 나타내는 두 줄이 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 크기 K × K인 모든 부분 행렬의 최댓값을 합한 값이다.

첫 번째 테스트 케이스의 행렬은 다음과 같다. 3 따라서 최댓값의 합은 3이다.

두 번째 테스트 케이스의 행렬은 다음과 같다. 9 3 1 6 따라서 최댓값의 합은 19이다.

세 번째 테스트 케이스의 행렬은 다음과 같다. 11 11 24 13 13 26 14 14 27