Problem Statement

You are developing a signature ramen, the "Rainbow Bowl", in which $N$ kinds of ingredients are lined up in a horizontal row. The topping positions are numbered from $1$ to $N$.
Here, for $1 \le i \le N-1$, position $i$ and position $i+1$ are adjacent to each other.
At each position, you place an ingredient from exactly $1$ of the $M$ ingredient categories.
The deliciousness when an ingredient of category $j$ ($1 \le j \le M$) is placed at position $i$ ($1 \le i \le N$) is $A_{ij}$.

This deliciousness becomes the satisfaction of the ramen.
However, if the ingredient category $j$ at some position $i$ ($1 \le i \le N$) is the same category $j$ as an adjacent ingredient, the flavor becomes monotonous and boring, so a penalty occurs. When a penalty occurs, the satisfaction from that ingredient becomes $A_{ij}-C$. As the shop's particular preference, the sense of rhythm created by deliberately placing the same category adjacently is also valued, so the total number of positions where a penalty occurs must be at least $X$.

The overall rating of the ramen depends on the moment of lowest satisfaction across the bites.
Among all placements of the $N$ ingredients satisfying the above condition, find the maximum possible value of the minimum of the $N$ satisfaction values.

Input

$N\ M\ C\ X$
$A_{11}\ A_{12} \ldots A_{1M}$
$\hspace{0.4cm}\vdots$
$A_{N1}\ A_{N2} \ldots A_{NM}$

・$2 \le N \le 2000\\$ ・$1 \le M \le 200\\$ ・$0 \le X \le N\\$ ・$1 \le C \le 10^9\\$ ・$1 \le A_{ij} \le 10^9\\$ ・All input values are integers

Output

Output the maximum possible value of the minimum of the $N$ satisfaction values.

Sample

4 3 26 1
72 81 47
29 97 2
75 25 82
84 17 56

55

6 3 28 3
57 39 18
11 79 6
40 68 68
16 40 63
93 49 91
10 55 68

35

3 2 50 2
10 20
15 5
30 25

-35