问题描述

有一个 $H$ 行 $W$ 列的网格，每个格子是 o、x 或 .。

可以将 . 改为 o（不能改 x）。问能否通过若干次操作使存在一行或一列中连续的 $K$ 个格子全为 o；若能，输出最少操作次数；否则输出 $-1$。

输入格式

第 1 行 $H$ $W$ $K$。

接下来 $H$ 行每行一个长度为 $W$ 的字符串。

输出格式

最少操作次数或 $-1$。

样例输入 1

3 4 3
xo.x
..o.
xx.o

样例输出 1

2

样例输入 2

4 2 3
.o
.o
.o
.o

样例输出 2

0

样例输入 3

3 3 3
x..
..x
.x.

样例输出 3

-1

样例输入 4

10 12 6
......xo.o..
x...x.....o.
x...........
..o...x.....
.....oo.....
o.........x.
ox.oox.xx..x
....o...oox.
..o.....x.x.
...o........

样例输出 4

3

评测数据规模

对于 $100\%$ 的数据，$1 \le H \times W \le 2 \times 10^5$，$1 \le K \le \max(H, W)$。