AT_gigacode_2019_d 家の建設

[problemUrl]: https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_d ギガ君は，パソコンを買い，プログラミングの勉強をし，会社に入り，金を儲け，そしてついに家を建設することとなりました！ 彼の住むテラ市は $ 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` と出力してください．ただし，家の面積と購入した長方形領域の面積は同じものとします．

入力は以下の形式で標準入力から与えられます． > $ 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\ \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 点) 追加の制約はない． ### Sample Explanation 1 彼は唯一のマスを購入し，家を建設すると，$ 200\ +\ 300\ =\ 500 $ 円かかり，ギリギリ足ります． この入力例は，小課題 $ 1 $ の制約を満たします． ### Sample Explanation 2 例えば，彼が以下のように土地を購入したとしましょう． !\[ \](https://img.atcoder.jp/gigacode-2019/addd712341465c2dbf4d87146acee3ed.png) その場合，土地を購入するのに $ 10\ +\ 20\ +\ 30\ +\ 40\ +\ 10\ +\ 20\ =\ 130 $ 円，家を建設するのに $ 6\ ×\ 10\ =\ 60 $ 円かかるため，合計で $ 130\ +\ 60\ =\ 190 $ 円必要ですが，$ 200 $ 円以下なので面積 $ 6 $ の家が建設可能です． なお，面積 $ 7 $ 以上の家を購入できるような方法はありません． この入力例は，小課題 $ 2 $ の制約を満たします． ### Sample Explanation 3 この入力例では，家を購入することができません．そのため，`0` と出力してください． !\[ \](https://img.atcoder.jp/gigacode-2019/79116d8ce624edee70da219561f150cb.png) ### Sample Explanation 4 例えば，以下のように土地を買い，面積 $ 9 $ の家を購入すると，$ 235 $ 円が必要となり，ギリギリ足ります． !\[ \](https://img.atcoder.jp/gigacode-2019/28a741cba8e6b8264e4761cc1e9bbee5.png)