AT_abc442_f [ABC442F] Diagonal Separation 2

There is a grid with $ N $ rows and $ N $ columns. The square at the $ i $ -th row from the top and $ j $ -th column from the left is denoted as square $ (i, j) $ . Each square in the grid is painted white or black. The information of the grid is given by $ N $ strings $ S_1, S_2, \ldots, S_N $ . If the $ j $ -th character of $ S_i $ is `.`, square $ (i, j) $ is painted white; if the $ j $ -th character of $ S_i $ is `#`, square $ (i, j) $ is painted black. You will repaint some squares so that both of the following conditions are satisfied: - For every row, the following condition holds: - There exists an integer $ k $ satisfying $ 0 \leq k \leq N $ such that the leftmost $ k $ squares of that row are painted white and the other squares are painted black. - For every column, the following condition holds: - There exists an integer $ k $ satisfying $ 0 \leq k \leq N $ such that the topmost $ k $ squares of that column are painted white and the other squares are painted black. Find the minimum number of squares that need to be repainted to satisfy the conditions.

The input is given from Standard Input in the following format: > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

Print the answer.

### Sample Explanation 1 You can satisfy the conditions by repainting square $ (2, 1) $ white and square $ (3, 3) $ black. ### Constraints - $ 1 \leq N \leq 5000 $ - $ N $ is an integer. - $ S_i $ is a string of length $ N $ consisting of `.` and `#`.