题目描述

quanjun最近疏于刷题而被巴里巴巴董事会惩罚去海岛上养鱼。

quanjun来到了一座小岛上，发现这座小岛的形状很特殊，是一个南北方向长 $n$ 米，东西方向长 $m$ 米的矩形。

小岛被划分成了一个个长度为 $1$ 米的正方形区域，被称作一个小单元。

我们可以把南北（上下）方向看成行，东西（左右）方向看成列，那么这个小岛可以看成一个 $n$ 行 $m$ 列的由小单元组成的矩形。

小单元只有两种类型：水域（用 . 表示）或者 陆地（用 * 表示）。

每一个水域和它上下左右相邻的四个小单元中的水域属于同一个连通块。

小岛最外面一圈的小单元（即所有处在第 $1$ 行、第 $n$ 行、第 $1$ 列或者第 $m$ 列上的小单元）和大海相邻。

如果一个水域所在的连通块中不存在任何一个水域和大海相邻（即这个连通块整体被陆地包围着），则我们称这个连通块是一个池塘。

因为池塘不和大海相邻，所以适合淡水养殖。

但是岛上的池塘太多了，每当雨季就会出现洪水泛滥的情况。

quanjun于是打电话咨询了水产养殖专家张漂亮。张漂亮的建议是，在这座小岛上维持恰好 $k$ 个池塘最佳。

于是quanjun开始采取”填水造陆”行动，具体来说，每次选择一个是水域的小单元，然后将这个小单元填上泥土，从而变成一个陆地小单元。

但是，quanjun的体力每天只能将一个水域小单元变成陆地小单元。

他希望能够使用最少的天数使得小岛上具有恰好 $k$ 个池塘。

请你帮助quanjun计算一下他最少需要几天？

输入格式

第一行，三个整数 $n, m, k(1 \le n,m \le 500; 0 \le k \le 500)$，分别表示小岛对应的行数、列数，以及最终需要的池塘的数量。

接下来 $n$ 行，每一行包含一个长度为 $m$ 的字符串，字符串仅由 . 和 * 构成，表示这个小岛初始的情况。

数据保证小岛上初始时的池塘数量至少有 $k$ 个。

输出格式

输出一个整数，表示quanjun至少要工作几天（即将几个水域小单元改成陆地小单元）才能使岛上恰好有 $k$ 个池塘。

5 4 1
****
*..*
****
**.*
..**

1

6 7 1
..*****
****..*
***...*
*.*****
*..*..*
*******

5

说明/提示

样例 1 解释

（接下来都用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的小单元）

最优方案是将 $(4,4)$ 的这一个水域小单元变成陆地，如下所示：

****
*..*
****
****
..**

此时还剩下一个池塘（由 $(2,2)$ 和 $(2,3)$ 构成）。

样例 2 解释

最优方案是将第 $(4,2)$，$(5,2)$，$(5,3)$，$(5,5)$，$(5,6)$ 这 $5$ 个水域小单元变成陆地，如下所示：

..*****
****..*
***...*
*******
*******
*******

此时还剩下 $1$ 个池塘。

数据规模与约定

• 对于 $20\%$ 的数据，$n,m,k \le 5$；
• 对于 $50\%$ 的数据，$n,m,k \le 50$；
• 对于 $100\%$ 的数据，$1 \le n,m \le 500; 0 \le k \le 500$。