AT_pakencamp_2025_day3_g Make T

$ x $ 座標と $ y $ 座標がそれぞれ $ 0 $ 以上 $ N $ 未満の整数であるような格子点 $ (x, y) $ に宇宙人が立っています（それ以外の場所には存在しません）。 合計 $ N^2 $ 人の宇宙人はそれぞれ 4 本の手を持っています。距離がちょうど $ 1 $ であるような $ 2 $ 人の宇宙人は、互いに手をつなぐ（双方向の接続を作る）ことができます。 初め、いくつかの宇宙人のペアはすでに手をつないでおり、その状態は以下のように与えられます。 - $ A_{i,j} = 1 $ のとき、 $ (i, j) $ にいる宇宙人と $ (i, j+1) $ にいる宇宙人はすでに手をつないでいます（ $ 0 \le i < N,\ 0 \le j < N-1 $ ）。 - $ B_{i,j} = 1 $ のとき、 $ (i, j) $ にいる宇宙人と $ (i+1, j) $ にいる宇宙人はすでに手をつないでいます（ $ 0 \le i < N-1,\ 0 \le j < N $ ）。 あなたは次の操作を $ 0 $ 回以上行うことができます。 - 距離がちょうど $ 1 $ である $ 2 $ 人の宇宙人を選び、その $ 2 $ 人に手をつながせる。 これらの操作を適切に行うことで、**ちょうど他の $ 3 $ 人の宇宙人と手をつないでいる宇宙人の数**を最大化してください。

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

ちょうど他の $ 3 $ 人の宇宙人と手をつないでいる宇宙人の最大数を出力せよ。

### お知らせ **この問題の想定解が誤っており、実際にはおそらく妥当な時間で解けないことが発覚しました。申し訳ありません。Universal Cupからもこの問題は削除されます。** なお、「宇宙人は最低2人の他の宇宙人と手を繋がなければならない」と条件をつければ妥当な出題であったと感じております。 ### Sample Explanation 1  図 1 の左側にサンプルの初期状態が示されています。図に示されている通り、追加で $ 12 $ 回手をつながせることで、合計 $ 8 $ 人の宇宙人がそれぞれちょうど $ 3 $ 人と手をつないでいる状態にすることができます。これは達成可能な最大値であり、最適です。 ### Constraints - $ 2 \le N \le 500 $ - $ A_{i,j} \in \lbrace 0,1\rbrace $ （ $ 0 \le i < N,\ 0 \le j < N-1 $ ） - $ B_{i,j} \in \lbrace 0,1\rbrace $ （ $ 0 \le i < N-1,\ 0 \le j < N $ ） - 入力はすべて整数