[SCOI2007]蜥蜴

在一个 $r$ 行 $c$ 列的网格地图中，分布着一些高度不同的石柱，其中部分石柱上站着蜥蜴。你的任务是让尽可能多的蜥蜴逃到地图边界之外。

网格中横向或纵向相邻位置之间的距离为 $1$。蜥蜴的最大跳跃距离为 $d$，即它可以跳到平面距离不超过 $d$ 的任意石柱上，也可以在跳跃距离允许时直接跳出地图。

石柱并不稳定。每当一只蜥蜴跳跃时，它离开的石柱高度会减少 $1$；如果蜥蜴仍落在地图内，则其到达的石柱高度不变。如果离开的石柱原高度为 $1$，那么蜥蜴离开后该石柱会消失，此后其他蜥蜴不能再落到该位置。

任何时刻，同一根石柱上都不能同时存在两只蜥蜴。

输入格式

第一行包含三个整数 $r,c,d$，分别表示地图的行数、列数和蜥蜴的最大跳跃距离。

接下来 $r$ 行描述石柱的初始状态。每行包含 $c$ 个字符，其中 $0$ 表示该位置没有石柱，$1\sim 3$ 表示该位置石柱的初始高度。

再接下来 $r$ 行描述蜥蜴的初始位置。每行包含 $c$ 个字符，其中 L 表示该位置有一只蜥蜴，. 表示该位置没有蜥蜴。

输出格式

输出一行一个整数，表示无法逃离地图的蜥蜴数量的最小值。

样例输入

5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........

样例输出

1

数据范围

• 对于 $100\%$ 的数据，$1\le r,c\le 20$；
• 对于 $100\%$ 的数据，$1\le d\le 4$。

来源与许可

本题为 SCOI 2007 试题「蜥蜴」，题面与测试数据整理自 BZOJ 1066。

样例 1

输入

5 8 2
00000000
02000000
00321100
02000000
00000000
........
........
..LLLL..
........
........

输出

1