PepperLa's Boast

PepperLa is a braggart(King of Blowing Cattle), which only means he has great lung capacity.

One day,the two-dimensional plane he lives is on fire.His current position is $(1,1)$, and the fire escape is at $(n,m)$. "Just a fire, why bother!" PepperLa boasted.

Because the fire is spreading quickly, once he starts running, he can't turn back. If his current position is $(x, y)$, he can only move forward to $(x+1,y+1)$ or $(x+1,y)$ or $(x,y+1)$ in one minute.

There is different volume of fresh air rested in each area. If an area's fresh air $\leq 0$, that means what left in the area is poisonous somke, PepperLa couldn't breath here.

Thanks to PepperLa's great lung capacity, each breath he can take in any volume of air and stored in his lung, he can hold the breath through poisonous smoke area. Each time, He can hold his breath for at most $K$ minutes, and cost $U$ volume of air.(If he doesn't hold the breath it cost no air, wow) He can start to hold his breath only if the air in his lung $>= U$.

Now PepperLa wonder whether he could survive so he could brag about his heroic experience. If PepperLa survives, he wants to know the maximum volume of air left in the lung when he comes to the exit.(the more air left, the more he can boast) If PepperLa couldn't escape, sadly, output -1.

There are multiple test cases in this problem.

For every test case, The first line has 4 interger, $N, M, K, U$ $(1 \leq N, M \leq 10^3,1 \leq K, U \leq 10^9)$

The next $N$ lines each line contains $M$ interger, the interger in $i$'th row, $j$'th column is volume of air rested in area $(i,j)\in[-10^9,10^9]$

The input guarantees that the air rested in area $(1,1),(n, m) > 0$, $\sum{N\times M}\leq 7 \times 10^6$

For each test case, output a single line contains one integer,representing for the answer.

3 4 2 1
1 0 0 9
0 -1 1 1
-1 0 2 1

4

(1,1)--hold breath->(2,2)--hold breath->(2,3)--->(3,3)--->(3,4)

when you at (1,1) you start to hold your breath, that's the first minute. The second minute, you walk through (2,2). Then you come to (2,3) and you can no longer hold your breath.

"红旗杯"第十四届东北地区大学生程序设计竞赛