問題文

$H$ 行 $W$ 列の二次元配列 $A$ が与えられます。この二次元配列に対し、交差値 $C_{i,j}$ を　$(i行目の和)\times(j列目の和)$、すなわち次のように定義します。

$$ C_{i,j} = \left(\sum_{k=1}^WA_{i,k}\right)\ \times\ \left(\sum_{l=1}^HA_{l,j}\right) $$

またこの二次元配列 $A$ に対しスコア $S$ を $C_{i,j}$ の最大値、すなわち次のように定義します。

$$ S = \max_{1 \le i \le H, 1 \le j \le W} C_{i,j} $$

$A$ に対し、次の操作を $0$ 回以上行う事を考えます。

• 任意の $i,j$ $(1 \le i \le H, 1 \le j \le W)$ を選ぶ。コスト $2^{B_{i,j}}$ を消費し $A_{i,j}$ を $+1$ する。

コストを $K$ まで消費できるとき、操作後の二次元配列 $A$ のスコア $S$ の最大値を求めてください。

制約

• $2 \le H,W \le 600$
• $1 \le K \le 2^{30}$
• $1 \le A_{i,j} \le 10^6$
• $0 \le B_{i,j} \le 30$
• 入力はすべて整数

入力

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

$H\ W\ K$
$A_{1,1}\ A_{1,2}\ \ldots\ A_{1,W} $
$A_{2,1}\ A_{2,2}\ \ldots\ A_{2,W} $
$\vdots$
$A_{H,1}\ A_{H,2}\ \ldots\ A_{H,W} $
$B_{1,1}\ B_{1,2}\ \ldots\ B_{1,W} $
$B_{2,1}\ B_{2,2}\ \ldots\ B_{2,W} $
$\vdots$
$B_{H,1}\ B_{H,2}\ \ldots\ B_{H,W} $

出力

操作後の $A$ のスコアの最大値を出力してください。最後に改行してください。

サンプル

2 2 6
1 2
3 4
1 1
2 2

64

1 3
3 5

5 6 67
6 5 46 35 48 5
34 1 20 46 45 5
41 19 38 49 30 22
32 48 41 12 38 24
30 4 8 37 15 37
1 0 4 1 2 2
2 3 4 4 0 2
3 3 1 4 0 2
0 4 0 3 0 1
4 3 3 1 3 4

64638