题目描述

李老师开始上信息课了。令人不省心的是，很多同学都在玩游戏。

机房的排为一排，共计 $N$ 台电脑。第 $i$ 名同学坐在从左到右第 $i$ 台电脑上。

信息课共计 $M$ 分钟，当 $A_{i,j}=1$ 时，第 $i$ 分钟，第 $j$ 名同学会玩游戏。

李老师会尽力阻止同学们玩游戏，假设李老师在某一分钟站在第 $i$ 名同学的身后，他就能监视到第 $\max(1,i-X) \sim \min(n,i+X)$ 名同学。

这分钟，李老师会增加 $K$ 的怒气值，其中 $K$ 是他能监视到的范围中，正在玩游戏的同学的数量。

李老师在每一分钟只能站在 $1$ 名同学身后，若李老师前一分钟站在第 $x$ 名同学身后，这一分钟站在第 $y$ 名同学身后，则李老师需要消耗 $|y-x|$ 点体力。由于年纪大了，李老师总计不会消耗超过 $T$ 点体力。

李老师在第 $1$ 时刻可能站在任意同学身后。

你是信息课代表，你想知道 $M$ 分钟过去（也就是下课时），李老师可能的最大怒气值会是多少。

输入格式

本题单个测试点内有多组测试数据。

第 $1$ 行，一个整数 $C$，表示测试数据的数量。

对于每组测试数据：

• 第 $1$ 行，$4$ 个正整数，表示 $N,M,X,T$。

• 第 $2 \sim M+1$ 行，每行 $N$ 个整数，表示数组 $A$。

输出格式

对于每组测试数据，输出 $1$ 行 $1$ 个正整数，表示李老师可能的最大怒气值。

2
3 1 0 1
0 1 0
8 2 1 2
1 1 1 0 0 0 0 1
0 0 1 1 1 0 0 1

1
6

提示

【样例解释】

对于第 $1$ 组测试数据，李老师只有在第 $1$ 分钟站在第 $2$ 名同学身后才能最大化答案，答案为 $1$。

对于第 $2$ 组测试数据，李老师只有在第 $1$ 分钟站在第 $2$ 名学身后，在第 $2$ 分钟站在第 $4$ 名同学身后，才能最大化答案，答案为 $6$。

注意：一名同学可能会多次使李老师的怒气值增加。

【数据范围】

测试点编号	$N$	$M$	$X$	$T$	特殊性质
$1 \sim 5$	$\le 8$			$\le 100$	无
$6 \sim 10$	$\le 100$
$11 \sim 15$	$\le 300$	$\le 300$	$\le 300$	$=0$
$16 \sim 20$	$\le 10$			$\le 300$
$21 \sim 25$	$\le 300$	$\le 10$
$26 \sim 30$		$\le 300$	$=0$		A
$31 \sim 50$			$\le 300$		无

特殊性质 A：保证对于 $i(1 \le i \le M)$，$A_{i,1}+A_{i,2}+ \dots + A_{i,N}=1$。

对于所有数据，保证：

• 除样例外，$C=5$。
• $0 \le N,M,X,T \le 300$。
• 对于 $i(1 \le i \le M),j(1 \le j \le N)$，$A_{i,j} \in \{0,1\}$。

【彩蛋】

某大型纪录片。