AT_past17_l 割引券

$ 1 $ から $ N $ までの番号がついた $ N $ 個の都市があります。 すべての相異なる都市同士の間には双方向に通行できる有料道路があります。また、すべての道路に使用できる割引券があり、これを使用すると通行料を安くすることができます。 都市 $ i $ と都市 $ j $ $ (i \lt j) $ を結ぶ道路の通行料は $ a_{i,j} $ 円で、割引券を使うと $ b_{i,j} $ 円になります。 $ (b_{i,j} \lt a_{i,j}) $ $ i \lt j $ を満たすすべての都市の組 $ (i, j) $ に対して次の値を求めてください。 - 割引券を合計 $ 1 $ 回以下使用して都市 $ i $ から都市 $ j $ へ移動するのに必要な最小の金額。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_{1,2} $ $ a_{1,3} $ $ \dots $ $ a_{1,N} $ $ a_{2,3} $ $ \dots $ $ a_{2,N} $ $ \vdots $ $ a_{N-1,N} $ $ b_{1,2} $ $ b_{1,3} $ $ \dots $ $ b_{1,N} $ $ b_{2,3} $ $ \dots $ $ b_{2,N} $ $ \vdots $ $ b_{N-1,N} $

答えを以下の形式で出力せよ。ここで $ c_{i,j} $ は 割引券を合計 $ 1 $ 回以下使用して都市 $ i $ から都市 $ j $ へ移動するのに必要な最小の金額を意味する。 > $ c_{1,2} $ $ c_{1,3} $ $ \dots $ $ c_{1,N} $ $ c_{2,3} $ $ \dots $ $ c_{2,N} $ $ \vdots $ $ c_{N-1,N} $

### Sample Explanation 1 例えば都市 $ 1 $ から都市 $ 3 $ へ割引券を合計 $ 1 $ 回以下使用して移動する場合は、次のように移動すれば $ 4 $ 円で移動することができて、これが最小です。 - 都市 $ 1 $ から都市 $ 4 $ へ割引券を利用して $ 1 $ 円掛けて移動する。 - 都市 $ 4 $ から都市 $ 3 $ へ割引券を利用せずに $ 3 $ 円掛けて移動する。 ### Constraints - $ 2 \leq N \leq 300 $ - $ 1 \leq b_{i,j} \lt a_{i,j} \leq 10^4 $ $ (i \lt j) $ - 入力される値はすべて整数