AT_abc442_f [ABC442F] Diagonal Separation 2

$ N $ 行 $ N $ 列のグリッドがあります。グリッドの上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i, j) $ と表記します。 グリッドの各マスは白または黒に塗られています。グリッドの情報は $ N $ 個の文字列 $ S_1, S_2, \ldots, S_N $ によって与えられ、 $ S_i $ の $ j $ 文字目が `.` のときマス $ (i, j) $ は白く塗られており、 $ S_i $ の $ j $ 文字目が `#` のときマス $ (i, j) $ は黒く塗られています。 あなたは、いくつかのマスの色を塗り替えて以下の条件をともに満たすようにします。 - すべての行に対して以下の条件が成り立つ。 - $ 0 \leq k \leq N $ を満たす整数 $ k $ が存在して、その行の左から $ k $ 個のマスは白く塗られており、その他のマスは黒く塗られている。 - すべての列に対して以下の条件が成り立つ。 - $ 0 \leq k \leq N $ を満たす整数 $ k $ が存在して、その列の上から $ k $ 個のマスは白く塗られており、その他のマスは黒く塗られている。 条件を満たすために塗り替える必要のあるマスの数として考えられる最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

答えを出力せよ。

### Sample Explanation 1 マス $ (2, 1) $ の色を白に、マス $ (3, 3) $ の色を黒に塗り替えることで条件を満たすことができます。 ### Constraints - $ 1 \leq N \leq 5000 $ - $ N $ は整数 - $ S_i $ は `.`, `#` からなる長さ $ N $ の文字列