AT_gigacode_2019_d 家の建設

吉加住的寺市用 $H$ 行 $W$ 列的方格表示。上起第 $i$ 行左起第 $j$ 列的方格用 $(i,j)$ 表示。另外，方格 $(i,j)$ 的地价是 $A_{i,j}$ 日元。 房子可以像下面这样建设： + 可以选择和购买寺市中的一些土地。购买方格 $(i,j)$ 需要 $A_{i,j}$ 日元。**另外，要购买的方格区域必须用一个长方形来表示**。 + 在购买的土地上**全部**建设房子。如果购买 $S$ 个方格，建房子需要 $S \times K$ 日元。 例如，当 $K=5$ 时，进行（图 $1$）那样的建设需要 $(1+4)+(2 \times 5)=15$ 日元，进行（图 $2$）那样的建设需要 $(6+3+4+1)+(4 \times 5)=34$ 日元。图中的数是各格的地价。 注意，不能购买（图 $3$）和（图 $4$）中灰色部分的土地。因为购买土地的区域不能用一个长方形来表示。 他现在有 $V$ 日元，可以用全部财产购买豪宅。他想买面积尽可能大的房子。 请求出他目前能想到的能买的房子最大的面积。另外，如果不能购买房子的话输出为 `0`。房子的面积和购买的长方形区域的面积是相同的。

第一行四个正整数 $H,W,K,V$。 接下来 $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)