/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 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})
- 入力はすべて整数
部分点
この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．
- (11 点) H = 1, W = 1
- (17 点) H = 1, W \leq 20
- (28 点) H \leq 20, W \leq 20
- (27 点) H \leq 75, W \leq 75
- (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 円が必要となり，ギリギリ足ります．
