003 - Agriculture

問題

山本くんは家庭菜園を始めるにあたって、土地の一区画を購入し、その区画内に畑を作ることを決めた。

南北に $H$ マス、東西に $W$ マスのマス目状に区切られた $H \times W$ 個の正方形の土地がある。
北から $i$ マス目、西から $j$ マス目 $(1 \leq i \leq H, 1 \leq j \leq W)$ の土地を土地 $i, j$ とする。
土地 $i, j$ には、唐辛子が栽培されているかの情報 $L_{i, j}$ と、その土地の値段 $V_{i, j}$ が与えられている。
土地 $i, j$ で唐辛子が栽培されている場合 $L_{i, j}$ は $1$ であり、そうでない場合 $L_{i, j}$ は $0$ である。

山本くんは次のような土地の一区画を購入する。

1. 唐辛子を栽培している土地が $1$ つも含まれない。
2. 正方形である。
3. 1, 2 を満たすものの中で最大である。
4. 3 を満たすものの中で費用が最小である。

ここで、任意の一区画を購入する際にかかる費用は、その区画内に含まれるすべての土地の値段の和である。
このとき、山本くんが支払う費用を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$
$L_{1,1}$ $\ldots$ $L_{1,W}$
$\vdots$
$L_{H,1}$ $\ldots$ $L_{H,W}$
$V_{1,1}$ $\ldots$ $V_{1,W}$
$\vdots$
$V_{H,1}$ $\ldots$ $V_{H,W}$

出力

山本くんが土地の一区画を購入できるなら費用の最小値を、購入できないなら $-1$ を出力せよ。
出力の最後には改行を入れること。

制約

全ての入力ケースについて以下を満たす。

• $1 \leq H, W \leq 10^3$
• $L_{i,j}$ は $0$ または $1$ である
• $0 \leq V_{i,j} \leq 10^5$
• 入力は全て整数である

入出力例

入力例1

3 3
1 0 0
0 0 0
1 1 1
2 3 5
7 2 4
1 5 7

出力例1

14

解説

このとき、山本くんは $2 \times 2$ の区画を購入するので $14$ が答えとなる。

---

入力例2

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
21 30 54 23 87
77 24 48 49 24
18 55 77 23 7

出力例2

-1

解説

購入できる区画が存在しないので、$-1$ を出力する。

---

入力例3

6 6
0 0 1 1 0 0
0 0 1 1 0 0
1 1 0 0 1 1
1 1 0 0 1 1
0 0 1 1 0 0
0 0 1 1 0 0
2 2 3 4 6 5
7 2 4 2 8 4
1 5 7 2 9 4
2 6 3 8 3 7
3 5 3 1 2 3
1 3 3 5 3 1

出力例3

9