题目背景

わがままで生きるくらいが　ちょうどいい　/　随心任性而活　这样就好

笑っていたい　いまいちでもいい　/　我想要微笑　就算不够完美也好

题目描述

Yuki 喜欢旅行。不过她是个宅女，所以她打算在提瓦特大陆旅行。

提瓦特大陆可以被看做一个 $n$ 行 $m$ 列的方格图，每个方格内都有一个整数 $a_{i,j}$。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的方格。

初始时，Yuki 有 $s$ 个摩拉。她会从方格图的第 $1$ 行选择一个方格作为旅程起点，开始她的旅程。

接下来，Yuki 可以进行若干次移动：

• 如果 Yuki 位于方格图的前 $(n-1)$ 行，则她可以移动到她左侧（如果存在）、右侧（如果存在）、下侧的方格；
• 如果 Yuki 位于方格图的第 $n$ 行，则她不可以再移动。

每次移动后，Yuki 的摩拉数量都会根据她当前位于的方格而变化。具体地，设 Yuki 移动后位于的方格为 $(i,j)$，则她的摩拉数量会发生如下的变化：

• 如果 $a_{i,j} \gt 0$，则 Yuki 的摩拉数量会增加 $a_{i,j}$；
• 如果 $a_{i,j} \lt 0$，则 Yuki 的摩拉数量会减少 $|a_{i,j}|$，即减少 $-a_{i,j}$；
• 如果 $a_{i,j}=0$，则 Yuki 的摩拉数量不会发生变化。

Yuki 可以重复经过同一个方格，并且在她每次经过某个方格时，她的摩拉数量都会变化。

如果在某次移动后，Yuki 的摩拉数量变成了负数，则她会被拘留，不可以再移动。

特殊地，Yuki 初始位于旅程起点时，她的摩拉数量也会根据她当前位于的方格而变化。同时，由于 Yuki 的背包大小有限，如果在某次移动后，她的摩拉数量大于 $k$，则她的摩拉数量会变为 $k$。

如果 Yuki 到达了方格图的第 $n$ 行且 Yuki 的摩拉数量不为负数，则我们称 Yuki 完成了她的旅程。

你需要帮助 Yuki 判断，她是否可以完成她的旅程；如果可以，你还需要求出，在她完成她的旅程后，她的摩拉数量的最大值。

输入格式

本题有多组测试数据。

第一行包含两个整数 $c,T$，分别表示测试点编号和测试数据组数。样例满足 $c=0$。

接下来依次输入每组测试数据。对于每组测试数据：

• 第一行包含四个整数 $n,m,s,k$。
• 接下来 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个整数表示 $a_{i,j}$。

输出格式

对于每组测试数据，输出一行，包含一个整数：

• 如果 Yuki 可以完成她的旅程，则输出在她完成她的旅程后，她的摩拉数量的最大值；
• 如果 Yuki 不可以完成她的旅程，则输出 $-1$。

样例 1 输入

0 2
3 3 1 5
2 -1 0
-3 -1 -1
-1 1 -2
2 3 1 3
-3 1 -1
0 -3 -2

样例 1 输出

4
-1

样例 1 解释

对于第 $1$ 组测试数据：

• 其中一种满足要求的移动路线为：$(1,1)\to(1,2)\to(1,1)\to(1,2)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$；
• 在移动过程中，Yuki 的摩拉数量的变化为：$1$（初始时的摩拉数量）$\to3\to2\to4\to3\to5\to4\to3\to4$；
• 可以证明，在 Yuki 完成她的旅程后，她的摩拉数量的最大值为 $4$。

对于第 $2$ 组测试数据，显然 Yuki 无法完成她的旅程。

样例 2

见题目附件中的 $\textit{journey/journey2.in}$ 与 $\textit{journey/journey2.ans}$。

该组样例满足测试点 $4$ 的限制。

样例 3

见题目附件中的 $\textit{journey/journey3.in}$ 与 $\textit{journey/journey3.ans}$。

该组样例满足测试点 $8$ 的限制。

样例 4

见题目附件中的 $\textit{journey/journey4.in}$ 与 $\textit{journey/journey4.ans}$。

该组样例满足测试点 $10$ 的限制。

样例 5

见题目附件中的 $\textit{journey/journey5.in}$ 与 $\textit{journey/journey5.ans}$。

该组样例满足测试点 $14$ 的限制。

样例 6

见题目附件中的 $\textit{journey/journey6.in}$ 与 $\textit{journey/journey6.ans}$。

该组样例满足测试点 $15$ 的限制。

样例 7

见题目附件中的 $\textit{journey/journey7.in}$ 与 $\textit{journey/journey7.ans}$。

该组样例满足测试点 $16$ 的限制。

样例 8

见题目附件中的 $\textit{journey/journey8.in}$ 与 $\textit{journey/journey8.ans}$。

该组样例满足测试点 $20$ 的限制。

数据范围

对于所有测试数据：

• $1\le T\le7$；
• $2\le n,m \le 1000$；
• $0 \le s \le k \le 10^9$；
• $-10^9 \le a_{i,j} \le 10^9$。

• 特殊性质 A：保证 $a_{i,j} \le 0$。
• 特殊性质 B：保证 $k=0$。
• 特殊性质 C：保证不存在 $i,j$ 满足 $1 \le i\lt n,1\le j \lt m$ 且 $a_{i,j}+a_{i,j+1}>0$。

提示

本题输入量较大，请使用较快的输入方式。