시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 1024 MB268531.250%

문제

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 A and B of length N, and two integers C and X. Then the entry Mij (for the ith row and jth column of the matrix) equals (Ai*i+Bj*j + C) mod X, where i and j are in the range [1, N].

입력

The first line of the input gives the number of test cases, TT test cases follow. Each test case begins with one line with four integers, NKC and X. Then there are two lines with N integers each, representing the arrays A and 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.

제한

  • 1 ≤ T ≤ 100.
  • 1 ≤ AiBi ≤ 100000.
  • 1 ≤ C ≤ 100000.
  • 1 ≤ X ≤ 1000000007.
  • 1 ≤ K ≤ N
  • 1 ≤ N ≤ 3000.

예제 입력 1

3
1 1 1 5
1
1
2 1 5 11
1 2
3 4
3 2 3 109
6 4 3
2 1 5

예제 출력 1

Case #1: 3
Case #2: 19
Case #3: 80

힌트

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.