题目描述

圣诞老人原本安排了 $N$ 支驯鹿队来拉雪橇。每支队伍有 $M$ 只驯鹿，但有些队伍还可能有 1 只备用驯鹿，因此最多有 $M+1$ 只。

为了识别驯鹿，原第 $i$ 支队伍中的第 $j$ 只驯鹿编号为：

$$(i-1)(M+1)+j,$$

其中 $i,j$ 均从 $1$ 开始。若 $j=M+1$，则表示该队的备用驯鹿；如果没有备用驯鹿，则该位置不存在。

每只驯鹿有一个重量，用一个 $N\times(M+1)$ 的矩阵 $W$ 表示：

• 若 $j\le M$，$W_{i,j}$ 表示原第 $i$ 支队伍中第 $j$ 只驯鹿的重量；
• $W_{i,M+1}$ 表示原第 $i$ 支队伍的备用驯鹿重量；若没有备用驯鹿，则为 $-1$。

现在圣诞老人决定解散所有原队伍，重新组队：

1. 每支新队伍必须恰好有 $M$ 只驯鹿；
2. 每只驯鹿最多属于一支新队伍，因此可以有驯鹿不被分配；
3. 新队伍不需要备用驯鹿。

圣诞老人希望最大化新队伍的净效能。净效能由两个整数参数 $A,B$ 决定：

• 每组成一支新队伍，增加 $A$ 点效能；
• 每支新队伍 $i$ 会产生 $B\cdot b(i)$ 的惩罚，其中 $b(i)$ 是该队伍的平衡值，定义为该队所有驯鹿重量和对 $M$ 取模。

假设最终组成 $K$ 支新队伍，其重量矩阵为 $W'$，则净效能为：

$$A\cdot K-\sum_{i=1}^{K}\left[B\cdot\left(\sum_{j=1}^{M}W'_{i,j}\bmod M\right)\right].$$

请构造一种新的组队方案，使净效能最大。

输入格式

输入第一行包含一个整数 $T$，表示测试用例数。

每个测试用例：

• 第一行包含四个整数 $N,M,A,B$；
• 接下来 $N$ 行，第 $i$ 行包含 $M+1$ 个整数：

$$W_{i,1},W_{i,2},\ldots,W_{i,M+1}.$$

输出格式

对于第 $i$ 个测试用例，先输出：

Case #i: value 

其中 value 是最大净效能

数据范围

$$1\le T\le70$$ $$1\le N\le200000$$ $$1\le M\le10000$$ $$1\le A,B\le10^9$$ $$1\le W_{i,1..M}\le10^9$$ $$1\le W_{i,M+1}\le10^9$$

或 $W_{i,M+1}=-1$，表示该队没有备用驯鹿。

每个测试用例中的驯鹿总数不超过 $200000$。

样例说明

第一组样例中，$N=2,M=3,A=14,B=11$。

存在 7 只驯鹿，编号分别为 $1,2,3,5,6,7,8$，重量分别为 $4,6,1,10,13,4,3$。

一种最优分队方式是：

• 不分配编号为 $1$ 的驯鹿；
• 将驯鹿 $3,5,6$ 组成一队，其重量和为 $1+10+13$，对 $3$ 取模为 $0$，没有惩罚；
• 将驯鹿 $8,2,7$ 组成一队，其重量和为 $3+6+4$，对 $3$ 取模为 $1$，产生 $11$ 点惩罚。

净效能为：

$$14\times2-(0+11)=17.$$

样例输入

4
2 3 14 11
4 6 1 -1
10 13 4 3
1 4 4 9
3 5 3 7 10
2 3 10 5
10 4 6 -1
1 4 7 -1
2 2 8 8
7 14 -1
13 5 -1

样例输出

Case #1: 17
Case #2: 0 
Case #3: 10 
Case #4: 8