【题目描述】

有 $T$ 组地图。每张地图有 $n$ 行 $m$ 列，格子中的非负整数表示魔物战斗力，$0$ 表示空地。

勇者从 $(s_x,s_y)$ 的空地出发，初始战斗力为 $P$。他可以在已经清空且上下左右连通的区域中移动。对于与该区域相邻、战斗力为 $x$ 的魔物：

• 当 $x\le P$ 时可以击败它；
• 击败后该格变为空地，勇者战斗力增加 $\lfloor x/k\rfloor$。

求勇者最终能达到的最大战斗力。

【输入格式】

$T$

$n$   $m$   $k$   $P$   $s_x$   $s_y$

$a_{1,1}$   $\cdots$   $a_{1,m}$

$\vdots$

【输出格式】

每组输出一行最终战斗力。

【样例】

1
3 3 2 5 2 2
8 4 10
3 0 6
20 5 7

35

【数据范围】

• $1\le T\le10$
• $1\le n,m\le300$
• $1\le k\le10^{18}$
• $0\le P,a_{i,j}\le10^{18}$
• $a_{s_x,s_y}=0$
• 单个输入文件格子总数不超过 $900000$
• 保证最终答案不超过 $10^{18}$