問題文

正の整数 $N, K$ と，非負整数 $A_1, A_2, \ldots, A_N$ および $B_1, B_2, \ldots, B_N$ が与えられます． ここで，$\sum_{i=1}^N A_i = \sum_{i=1}^N B_i = K$ が成り立つとします．

以下の条件をみたす行列全体の集合を $G$ とします．

• サイズが $N \times N$ である．
• 全ての要素が非負整数である．
• $i = 1, \ldots, N$ について，$i$ 行目の要素の和が $A_i$ に等しい．
• $i = 1, \ldots, N$ について，$i$ 列目の要素の和が $B_i$ に等しい．

全ての要素が非負整数であるサイズ $N \times N$ の行列 $P$ が与えられるので， $\min_{Q \in G} \| P-Q \|_\mathrm{F}^2$ を求めて下さい．

ただし，$\| \cdot \|_\mathrm{F}$ は行列のフロべニウスノルムであり， サイズ $N \times N$ の行列 $R$ について $\| R \|_\mathrm{F} := \sqrt{\sum_{i=1}^N \sum_{j=1}^N R_{i, j}^2}$ で定義されます．

また，本問題の条件のもとで $G$ は非空であることが証明できるため，$\min_{Q \in G} \| P-Q \|_\mathrm{F}^2$ は必ず定義されます．

入力

$N\ K$
$A_1\ A_2\ \ldots\ A_N$
$B_1\ B_2\ \ldots\ B_N$
$P_{1, 1}\ P_{1, 2}\ \ldots\ P_{1, N}$
$P_{2, 1}\ P_{2, 2}\ \ldots\ P_{2, N}$
$\vdots$
$P_{N, 1}\ P_{N, 2}\ \ldots\ P_{N, N}$

出力

最後に改行してください。

サンプル

2 3
1 2
2 1
1 1
1 1

1

2 4
2 2
3 1
2 0
1 1

0

3 6
2 2 2
4 1 1
3 2 1
1 8 10
2 3 5

171