CF78E.Evacuation

They've screwed something up yet again... In one nuclear reactor of a research station an uncontrolled reaction is in progress and explosion which will destroy the whole station will happen soon.

The station is represented by a square n × n divided into 1 × 1 blocks. Each block is either a reactor or a laboratory. There can be several reactors and exactly one of them will explode soon. The reactors can be considered impassable blocks, but one can move through laboratories. Between any two laboratories, which are in adjacent blocks, there is a corridor. Blocks are considered adjacent if they have a common edge.

In each laboratory there is some number of scientists and some number of rescue capsules. Once the scientist climbs into a capsule, he is considered to be saved. Each capsule has room for not more than one scientist.

The reactor, which is about to explode, is damaged and a toxic coolant trickles from it into the neighboring blocks. The block, which contains the reactor, is considered infected. Every minute the coolant spreads over the laboratories through corridors. If at some moment one of the blocks is infected, then the next minute all the neighboring laboratories also become infected. Once a lab is infected, all the scientists there that are not in rescue capsules die. The coolant does not spread through reactor blocks.

There are exactly t minutes to the explosion. Any scientist in a minute can move down the corridor to the next lab, if it is not infected. On any corridor an unlimited number of scientists can simultaneously move in both directions. It is believed that the scientists inside a lab moves without consuming time. Moreover, any scientist could get into the rescue capsule instantly. It is also believed that any scientist at any given moment always has the time to perform their actions (move from the given laboratory into the next one, or climb into the rescue capsule) before the laboratory will be infected.

Find the maximum number of scientists who will be able to escape.

他们又搞砸了……某科研站的一座核反应堆中正发生失控反应，不久后将发生爆炸，整个站点都将被摧毁。

该站点由一个 $ n \times n $ 的正方形网格表示，网格被划分为若干 $ 1 \times 1 $ 的方块。每个方块要么是反应堆，要么是实验室。可能存在多个反应堆，但其中恰好有一个即将爆炸。反应堆可视为不可通行的障碍物，而实验室则允许通行。任意两个位于相邻方块中的实验室之间均有一条走廊。若两个方块具有公共边，则称其为相邻。

每个实验室中均有一定数量的科学家和一定数量的救援舱。一旦一名科学家进入一个救援舱，即视为获救。每个救援舱最多容纳一名科学家。

即将爆炸的反应堆已受损，有毒冷却剂正从中渗出并蔓延至邻近方块。包含该反应堆的方块被视为已被感染。此后，冷却剂每分钟通过走廊向实验室区域扩散：若在某一时刻某个方块已被感染，则下一分钟所有与其相邻的实验室也将被感染。一旦某个实验室被感染，其中所有尚未进入救援舱的科学家将立即死亡。冷却剂无法穿过反应堆方块。

距离爆炸仅剩 $ t $ 分钟。每分钟内，任何科学家均可沿走廊移动至相邻实验室（前提是该实验室尚未被感染）。每条走廊上可同时有任意数量的科学家双向通行。假设科学家在实验室内部移动不消耗时间。此外，任何科学家均可瞬间进入救援舱。还假设：在任意给定时刻，每位科学家总有足够的时间完成其操作（即从当前实验室移动至相邻实验室，或进入救援舱），且该操作总能在实验室被感染之前完成。

求能够成功逃生的科学家的最大人数。

The first line contains two integers n and t (2 ≤ n ≤ 10, 1 ≤ t ≤ 60). Each of the next n lines contains n characters. These lines describe the scientists' locations. Then exactly one empty line follows. Each of the next n more lines contains n characters. These lines describe the rescue capsules' locations.

In the description of the scientists' and the rescue capsules' locations the character "Y" stands for a properly functioning reactor, "Z" stands for the malfunctioning reactor. The reactors' positions in both descriptions coincide. There is exactly one malfunctioning reactor on the station. The digits "0" - "9" stand for the laboratories. In the description of the scientists' locations those numbers stand for the number of scientists in the corresponding laboratories. In the rescue capsules' descriptions they stand for the number of such capsules in each laboratory.

第一行包含两个整数 $n$ 和 $t$（$2 \leq n \leq 10$，$1 \leq t \leq 60$）。接下来的 $n$ 行，每行包含 $n$ 个字符，描述科学家的位置。随后恰好有一行空行。再接下来的 $n$ 行，每行也包含 $n$ 个字符，描述救援舱的位置。

在科学家位置和救援舱位置的描述中，字符 "Y" 表示运行正常的反应堆，"Z" 表示发生故障的反应堆。两处描述中反应堆的位置完全一致。空间站上恰好存在一个发生故障的反应堆。数字字符 "0"–"9" 表示各个实验室：在科学家位置的描述中，这些数字表示对应实验室中的科学家人数；在救援舱位置的描述中，这些数字表示对应实验室中的救援舱数量。

Print a single number — the maximum number of scientists who will manage to save themselves.

输出一个整数——成功自救的科学家的最大人数。

In the second sample the events could take place as follows:

在第二个样例中，事件可能发生如下：