AT_abc442_f.[ABC442F] Diagonal Separation 2

有一个 $N$ 行 $N$ 列的网格。从上往下第 $i$ 行、从左往右第 $j$ 列的方格记为 $(i, j)$。

网格中的每个方格都被涂成白色或黑色。网格的信息由 $N$ 个字符串 $S_1, S_2, \dots, S_N$ 给出。如果 $S_i$ 的第 $j$ 个字符是 .，则方格 $(i, j)$ 为白色；如果 $S_i$ 的第 $j$ 个字符是 #，则方格 $(i, j)$ 为黑色。

你需要对某些方格进行重新涂色，使得以下两个条件均满足：

1. 对于每一行，都满足以下条件：
   存在一个整数 $k$ ($0 \le k \le N$)，使得该行最左侧的 $k$ 个方格被涂成白色，而该行其余方格被涂成黑色。
2. 对于每一列，都满足以下条件：
   存在一个整数 $k$ ($0 \le k \le N$)，使得该列最上方的 $k$ 个方格被涂成白色，而该列其余方格被涂成黑色。

求满足上述条件所需重新涂色的方格的最小数量。

输入从标准输入按以下格式给出：

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

限制条件

• $1 \le N \le 5000$
• $N$ 是整数。
• $S_i$ 是长度为 $N$ 的字符串，由 . 和 # 组成。

打印答案。

样例 1 解释

你可以通过将方格 $(2,1)$ 重新涂成白色，并将方格 $(3,3)$ 重新涂成黑色来满足条件。