题目描述

给定一个 $N \times N$ 的非负整数方阵 $M$。我们希望列出 $M$ 中所有 $K \times K$ 的子矩阵的最大值，然后求出这些值之和。（注意，$M$ 的同一元素可能作为多个子矩阵的最大值出现，此时它将在列表中出现多次。）你能求出这个总和吗？

为了简化矩阵的输入，给定两个长度为 $N$ 的数组 $\mathbf{A}$ 和 $\mathbf{B}$，以及两个整数 $\mathbf{C}$ 和 $\mathbf{X}$。矩阵元素 $M_{ij}$（第 $i$ 行第 $j$ 列）等于 $(\mathbf{A}_i \times i + \mathbf{B}_j \times j + \mathbf{C}) \pmod{\mathbf{X}}$，其中 $i$ 和 $j$ 的取值范围为 $[1, N]$。

输入格式

第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例首先是一行包含四个整数 $N$、$K$、$C$ 和 $X$。然后有两行，每行包含 $N$ 个整数，分别表示数组 $\mathbf{A}$ 和 $\mathbf{B}$。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有 $K \times K$ 子矩阵的最大值之和。

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

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

提示

在第一个测试用例中，矩阵为：

3

因此最大值之和为 $3$。

在第二个测试用例中，矩阵为：

9 3
1 6

因此最大值之和为 $19$。

在第三个测试用例中，矩阵为：

11 11 24
13 13 26
14 14 27

限制

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

小数据集（测试集 1 - 可见）

$1 \le N \le 50$。

大数据集（测试集 2 - 隐藏）

$1 \le N \le 3000$。

翻译由 DeepSeek V4 Pro 完成