题目描述

有一个 30 行 30 列的矩阵，每个格子是 ‘o’ 或者是 ‘.’ 。其中前者表示有一枚银币，后者表示没有银币。下面的两个步骤合起来，称为一次操作：

首先，你选择一个方向：上、下、左、右。

然后，把所有的银币往你选择的方向移动一格。如果这个操作会使某些银币越出了矩阵的界，那么越界的银币会自动消失。

你现在的任务是：用最少的操作次数，使得矩阵里剩下的银币数量恰好是K，输出最少的操作次数。如果不可能完成任务，输出 -1 。

输入格式

第一行，三个整数 $r$、$c$、$k$。$1 \le r,c \le 30$ , $1 \le k \le 900$。

接下来是 $r$ 行 $c$ 列的矩阵。

输出格式

一个整数。

样例

3 4 3
.o..
oooo
..o.

2

6 6 12
.....o
......
oooooo
oooooo
......
o.....

3

样例解释

样例 1 解释：其中一种最优方案是:向右移动两次

样例 2 解释：其中一种最优方案是:向上移动，向下移动，向下移动