問題文

あなたは $N$ 種類の具材を横一列に並べる、名物ラーメン「レインボー盛り」を開発しており、トッピングの位置には $1$ から $N$ までの番号が付けられている。
ここで、$1 \le i \le N-1$ において、位置 $i$ と位置 $i+1$ は互いに隣り合っている。
各位置には $M$ 種類の食材カテゴリのうち、いずれか $1$ つを配置する。
位置 $i$ ($1 \le i \le N$) に食材カテゴリ $j$ ($1 \le j \le M$) の食材を置いたときのおいしさは $A_{ij}$ である。

このおいしさがラーメンの満足度となる。
しかし、ある位置 $i$ ($1 \le i \le N$) の食材カテゴリ $j$ が、隣り合う食材と同じカテゴリ $j$ である場合、味が単調になり飽きるため、ペナルティが発生する。 ペナルティが発生するとその食材による満足度は $A_{ij}-C$ になる。 店のこだわりとして、あえて同じカテゴリを隣接させることで生まれるリズム感も重視しているため、ペナルティが発生する位置の総数は、 $X$ 以上でなければならない。

ラーメンの総合評価は、一口食べたときの最も満足度が低かった瞬間に左右される。
上記の制約を満たすような $N$ 個の食材の配置について、 $N$ 個の満足度の最小値としてありえる最大値を求めよ。

入力

$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\\$ ・入力はすべて整数

出力

$N$ 個の満足度の最小値としてありえる最大値を出力してください。

サンプル

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