配点: $100$ 点

問題文

ギガ君は，パソコンを買い，プログラミングの勉強をし，会社に入り，金を儲け，そしてついに家を建設することとなりました！
彼の住むテラ市は $H$ 行 $W$ 列のマス目で表されます．上から $i$ 行目，左から $j$ 列目のマスは $(i, j)$ で表されます．また，マス $(i, j)$ の地価は $A_{i, j}$ 円です．

さて，家は以下のように建設することができます．

• テラ市の中のいくつかのマス（土地）を選び，購入することができる．マス $(i, j)$ を購入するのに $A_{i, j}$ 円かかる．なお，購入するマスの領域は 1 つの長方形で表されなければならない．
• 購入した土地全体に家を建設する．$S$ 個のマスを購入した場合，家を建設するのに $S×K$ 円かかる．

例えば，$K = 5$ であるとき，(図1) のような建設を行う場合は $(1+4)+(2 \\times 5)=15$ 円，(図2) のような建設を行う場合は $(6+3+4+1)+(4 \\times 5)=34$ 円かかります．ただし図中の数は各マスの地価とします．

また，以下の (図3) や (図4) の灰色の部分の土地を購入することはできません．なぜなら，購入した土地の領域が $1$ つの長方形で表されないからです．

彼は現在 $V$ 円持っており，全財産を豪邸の購入に使うことができます．彼はできるだけ面積の大きい家を買いたいです．
現在彼が買うことのできる家として考えられる，最大の面積を求めてください．また，家を購入できない場合は 0 と出力してください．ただし，家の面積と購入した長方形領域の面積は同じものとします．

制約

• $1 \\leq H, W \\leq 125$
• $1 \\leq A_{i, j}$, $K \\leq 1 \\ 000 \\ 000 \\ 000$
• $1 \\leq V \\leq 1 \\ 000 \\ 000 \\ 000 \\ 000 \\ 000 (=10^{15})$
• 入力はすべて整数

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

1. (11 点) $H = 1, W = 1$
2. (17 点) $H = 1, W \\leq 20$
3. (28 点) $H \\leq 20, W \\leq 20$
4. (27 点) $H \\leq 75, W \\leq 75$
5. (17 点) 追加の制約はない．

---

入力

入力は以下の形式で標準入力から与えられます．

$H$ $W$ $K$ $V$ $A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ ... $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ ... $A_{2, W}$ $A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ ... $A_{3, W}$ $:$ $A_{H, 1}$ $A_{H, 2}$ $A_{H, 3}$ ... $A_{H, W}$

出力

彼が買うことのできる家として考えられる，最大の面積を求めてください．
ただし，家を購入できない場合は 0 と出力してください．

---

入力例 1

1 1 200 500
300

出力例 1

1

彼は唯一のマスを購入し，家を建設すると，$200 + 300 = 500$ 円かかり，ギリギリ足ります．
この入力例は，小課題 $1$ の制約を満たします．

---

入力例 2

1 8 10 200
30 40 10 20 30 40 10 20

出力例 2

6

例えば，彼が以下のように土地を購入したとしましょう．

その場合，土地を購入するのに $10 + 20 + 30 + 40 + 10 + 20 = 130$ 円，家を建設するのに $6 × 10 = 60$ 円かかるため，合計で $130 + 60 = 190$ 円必要ですが，$200$ 円以下なので面積 $6$ の家が建設可能です．
なお，面積 $7$ 以上の家を購入できるような方法はありません．
この入力例は，小課題 $2$ の制約を満たします．

---

入力例 3

5 5 10 17
12 19 25 13 25
14 16 18 11 10
19 17 24 26 12
23 11 16 19 14
18 23 27 11 16

出力例 3

0

この入力例では，家を購入することができません．そのため，0 と出力してください．

---

入力例 4

4 7 10 240
17 12 15 18 19 15 23
22 12 41 16 27 10 10
15 69 18 11 10 23 15
12 20 13 12 17 18 15

出力例 4

9

例えば，以下のように土地を買い，面積 $9$ の家を購入すると，$235$ 円が必要となり，ギリギリ足ります．