他们又搞砸了......在一个研究站的一个核反应堆中,一种不受控制的反应正在进行中,很快就会发生摧毁整个空间站的爆炸。
该站由一个 n × n 的正方形表示,分为 1 × 1 块。每个区块要么是一个反应堆,要么是一个实验室。可能有多个反应堆,而其中一个很快就会爆炸。反应堆可以被认为是不可通行的方块,但可以穿过实验室。任何两个相邻街区的实验室之间都有一条走廊。如果块具有公共边,则它们被认为是相邻的。
每个实验室都有一定数量的科学家和一定数量的救援舱。一旦科学家爬进太空舱,他就被认为得救了。每个太空舱最多可容纳一名科学家。
即将爆炸的反应堆被损坏,有毒的冷却剂从其中滴入邻近的区块。包含反应堆的区块被认为已被感染。每分钟冷却剂都会通过走廊遍布实验室。如果某个时刻其中一个区块被感染,那么下一分钟所有邻近的实验室也会被感染。一旦实验室被感染,所有不在救援舱中的科学家都会死亡。冷却剂不会通过反应堆块扩散。
距离爆炸正好 t 分钟。如果没有被感染,任何科学家都可以在一分钟内沿着走廊移动到下一个实验室。在任何走廊上,无限数量的科学家可以同时向两个方向移动。人们相信,实验室里的科学家们在移动时不会浪费时间。此外,任何科学家都可以立即进入救援舱。人们还相信,在实验室被感染之前,任何科学家在任何给定时刻总是有时间执行他们的行动(从给定实验室移动到下一个实验室,或爬进救援舱)。
找出能够逃脱的科学家的最大数量。
输入
第一行包含两个整数 n 和 t (2 ≤ n ≤ 10, 1 ≤ t ≤ 60)。接下来的 n 行每行包含 n 个字符。这些线描述了科学家的位置。然后紧接着就是一个空行。接下来的 n 个行中的每一行都包含 n 个字符。这些线描述了救援舱的位置。
在对科学家和救援舱位置的描述中,字符“Y”代表正常运行的反应堆,“Z”代表故障反应堆。两种描述中反应堆的位置是一致的。空间站上只有一个发生故障的反应堆。数字“0”-“9”代表实验室。在对科学家位置的描述中,这些数字代表相应实验室中科学家的数量。在救援舱的描述中,它们代表每个实验室中此类救援舱的数量。
输出
打印一个数字——能够自救的科学家的最大数量。
示例
输入 #1
3 3 1YZ 1YY 100 0YZ 0YY 003
输出 #1
2
输入 #2
4 4 Y110 1Y1Z 1Y0Y 0100 Y001 0Y0Z 0Y0Y 0005
输出 #2
3
注意
在第二个示例中,事件可能发生如下: