Background

Living selfishly is just about right.

I want to keep smiling, even if it's not perfect.

Description

Yuki loves to travel. However, since she is a homebody, she plans to travel across the continent of Teyvat.

The continent of Teyvat can be viewed as a grid with $n$ rows and $m$ columns, where each cell contains an integer $a_{i,j}$. We denote the cell in the $i$-th row and $j$-th column as $(i,j)$.

Initially, Yuki has $s$ Mora. She chooses a cell in the first row of the grid as her starting point to begin her journey.

Next, Yuki can perform a series of moves:

• If Yuki is in one of the first $(n-1)$ rows, she can move to the cell to her left (if it exists), to her right (if it exists), or to the cell directly below her.
• If Yuki is in the $n$-th row, she cannot move anymore.

After each move, Yuki's amount of Mora changes based on the cell she is currently in. Specifically, if Yuki moves to cell $(i,j)$, her Mora changes as follows:

• If $a_{i,j} > 0$, Yuki's Mora increases by $a_{i,j}$.
• If $a_{i,j} < 0$, Yuki's Mora decreases by $|a_{i,j}|$, i.e., it decreases by $-a_{i,j}$.
• If $a_{i,j} = 0$, Yuki's Mora remains unchanged.

Yuki can visit the same cell multiple times, and her Mora will change every time she visits a cell.

If at any point after a move Yuki's Mora becomes negative, she is detained and cannot move anymore.

Specifically, when Yuki is at her starting point, her Mora also changes based on the value of that cell. Additionally, because Yuki's bag has a limited capacity, if her Mora exceeds $k$ after any move, her Mora becomes $k$.

If Yuki reaches the $n$-th row and her Mora is not negative, we say Yuki has completed her journey.

You need to help Yuki determine if she can complete her journey. If she can, you also need to find the maximum amount of Mora she can have after completing her journey.

Input

The input contains multiple test cases.

The first line contains two integers $c$ and $T$, representing the test case ID and the number of test cases, respectively. The sample satisfies $c=0$.

Each test case is provided as follows:

• The first line contains four integers $n, m, s, k$.
• The next $n$ lines each contain $m$ integers, where the $j$-th integer in the $i$-th line represents $a_{i,j}$.

Output

For each test case, output a single line containing one integer:

• If Yuki can complete her journey, output the maximum amount of Mora she can have after completing her journey.
• If Yuki cannot complete her journey, output $-1$.

Examples

Input 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

Output 1

4
-1

Note 1

For the first test case:

• One possible path is: $(1,1)\to(1,2)\to(1,1)\to(1,2)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.
• During the movement, Yuki's Mora changes as follows: $1$ (initial) $\to 3 \to 2 \to 4 \to 3 \to 5 \to 4 \to 3 \to 4$.
• It can be proven that the maximum amount of Mora Yuki can have after completing her journey is $4$.

For the second test case, it is clear that Yuki cannot complete her journey.

Examples 2-8

See the files $\textit{journey/journey2.in}$ through $\textit{journey/journey8.in}$ and their corresponding $\textit{.ans}$ files in the problem attachments. These samples satisfy the constraints for test points 4, 8, 10, 14, 15, 16, and 20, respectively.

Constraints

For all test cases:

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

• Special Property A: Guaranteed $a_{i,j} \le 0$.
• Special Property B: Guaranteed $k=0$.
• Special Property C: Guaranteed that there exist no $i, j$ such that $1 \le i < n, 1 \le j < m$ and $a_{i,j} + a_{i,j+1} > 0$.

Note

The input size for this problem is large; please use fast I/O methods.