{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.\n\nIn 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.\n\nThe 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.\n\nThere 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.\n\nFind the maximum number of scientists who will be able to escape."},{"iden":"input","content":"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.\n\nIn 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."},{"iden":"output","content":"Print a single number — the maximum number of scientists who will manage to save themselves."},{"iden":"examples","content":"Input\n\n3 3\n1YZ\n1YY\n100\n\n0YZ\n0YY\n003\n\nOutput\n\n2\n\nInput\n\n4 4\nY110\n1Y1Z\n1Y0Y\n0100\n\nY001\n0Y0Z\n0Y0Y\n0005\n\nOutput\n\n3"},{"iden":"note","content":"In the second sample the events could take place as follows:\n\n<center>![image](https://espresso.codeforces.com/c29057a40dc0748af4c671a35415c2ff5fde2be5.png)</center>"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"他们又把事情搞砸了……在研究站的一个核反应堆中，一场失控的链式反应正在进行，很快就会发生爆炸，摧毁整个站点。\\n\\n站点被表示为一个大小为 #cf_span[n × n] 的正方形，划分为 #cf_span[1 × 1] 的格子。每个格子要么是反应堆，要么是实验室。可能存在多个反应堆，但只有一个会很快爆炸。反应堆被视为不可通行的格子，但可以通过实验室移动。任意两个位于相邻格子的实验室之间都有一条走廊。如果两个格子有公共边，则认为它们相邻。\\n\\n每个实验室中都有一定数量的科学家和一定数量的救生舱。一旦科学家进入救生舱，他就被视为获救。每个救生舱最多容纳一名科学家。\\n\\n即将爆炸的反应堆受损，有毒冷却剂从其内部渗出并流入相邻的格子。包含反应堆的格子被视为已感染。每分钟，冷却剂通过走廊在实验室中扩散。如果某一时刻某个格子被感染，则下一分钟所有相邻的实验室也会被感染。一旦实验室被感染，其中尚未进入救生舱的所有科学家都会死亡。冷却剂不会通过反应堆格子传播。\\n\\n距离爆炸还有恰好 #cf_span[t] 分钟。任何科学家在一分钟内可以沿着走廊移动到下一个实验室，前提是该实验室尚未被感染。任何走廊上可以同时有无限多名科学家双向移动。科学家在实验室内部移动被认为不消耗时间。此外，任何科学家可以瞬间进入救生舱。同时，假定任何科学家在任何时刻都有足够的时间完成其动作（从当前实验室移动到相邻实验室，或进入救生舱），在实验室被感染之前完成。\\n\\n求出能够成功逃生的科学家的最大数量。\\n\\n第一行包含两个整数 #cf_span[n] 和 #cf_span[t]（#cf_span[2 ≤ n ≤ 10]，#cf_span[1 ≤ t ≤ 60]）。接下来的 #cf_span[n] 行每行包含 #cf_span[n] 个字符，描述科学家的位置。随后恰好有一行空行。接下来的 #cf_span[n] 行每行包含 #cf_span[n] 个字符，描述救生舱的位置。\\n\\n在科学家位置和救生舱位置的描述中，字符 \\\"_Y_\\\" 表示正常工作的反应堆，\\\"_Z_\\\" 表示故障的反应堆。两组描述中的反应堆位置一致。站点中恰好有一个故障反应堆。数字 \\\"_0_\\\" - \\\"_9_\\\" 表示实验室。在科学家位置描述中，这些数字表示对应实验室中的科学家数量；在救生舱位置描述中，它们表示每个实验室中救生舱的数量。\\n\\n请输出一个数字——能够成功逃生的科学家的最大数量。\\n\\n在第二个样例中，事件可能发生如下：\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含两个整数 #cf_span[n] 和 #cf_span[t]（#cf_span[2 ≤ n ≤ 10]，#cf_span[1 ≤ t ≤ 60]）。接下来的 #cf_span[n] 行每行包含 #cf_span[n] 个字符，描述科学家的位置。随后恰好有一行空行。接下来的 #cf_span[n] 行每行包含 #cf_span[n] 个字符，描述救生舱的位置。在科学家位置和救生舱位置的描述中，字符 \\\"_Y_\\\" 表示正常工作的反应堆，\\\"_Z_\\\" 表示故障的反应堆。两组描述中的反应堆位置一致。站点中恰好有一个故障反应堆。数字 \\\"_0_\\\" - \\\"_9_\\\" 表示实验室。在科学家位置描述中，这些数字表示对应实验室中的科学家数量；在救生舱位置描述中，它们表示每个实验室中救生舱的数量。\"},{\"iden\":\"output\",\"content\":\"请输出一个数字——能够成功逃生的科学家的最大数量。\"},{\"iden\":\"examples\",\"content\":\"输入\\n3 3\\n1YZ\\n1YY\\n100\\n0YZ\\n0YY\\n003\\n\\n输出\\n2\\n\\n输入\\n4 4\\nY110\\n1Y1Z\\n1Y0Y\\n0100\\nY001\\n0Y0Z\\n0Y00\\n0005\\n\\n输出\\n3\"},{\"iden\":\"note\",\"content\":\"在第二个样例中，事件可能发生如下：   \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ t \\in \\mathbb{Z} $ be the grid size and time until explosion, respectively.  \nLet $ G = (V, E) $ be the grid graph of size $ n \\times n $, where each cell $ (i,j) \\in \\{1,\\dots,n\\}^2 $ is a vertex.  \nLet $ R \\subset V $ be the set of reactor blocks (impassable), with exactly one malfunctioning reactor $ r_0 \\in R $.  \nLet $ L = V \\setminus R $ be the set of laboratory blocks (passable).  \n\nFor each laboratory block $ \\ell \\in L $:  \n- Let $ s_\\ell \\in \\{0,1,\\dots,9\\} $ denote the number of scientists initially in $ \\ell $.  \n- Let $ c_\\ell \\in \\{0,1,\\dots,9\\} $ denote the number of rescue capsules in $ \\ell $.  \n\nLet $ d(\\ell, r_0) $ denote the shortest path distance (in grid steps, through $ L $) from laboratory $ \\ell $ to the malfunctioning reactor $ r_0 $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10 $  \n2. $ 1 \\leq t \\leq 60 $  \n3. $ |R| \\geq 1 $, and exactly one $ r_0 \\in R $ is the source of infection.  \n4. $ s_\\ell, c_\\ell \\in \\mathbb{Z}_{\\geq 0} $ for all $ \\ell \\in L $.  \n5. Infection spreads in discrete time steps: at time $ \\tau \\in \\{0,1,\\dots,t\\} $, all laboratories $ \\ell \\in L $ with $ d(\\ell, r_0) \\leq \\tau $ are infected.  \n6. Scientists may move along edges of $ L $ (corridors) in any direction, with unlimited capacity and zero time cost.  \n7. A scientist may enter a rescue capsule only if the laboratory containing the capsule is not yet infected at the time of entry.  \n8. Each capsule can save at most one scientist.  \n\n**Objective**  \nMaximize the total number of scientists saved, i.e., find the maximum number of scientists that can reach some laboratory $ \\ell \\in L $ with $ d(\\ell, r_0) > t $, or reach a laboratory $ \\ell $ with $ d(\\ell, r_0) \\leq t $ **before** it becomes infected, and enter a capsule there, subject to capsule capacity constraints.  \n\nFormally, define the set of **safe laboratories**:  \n$$ S = \\{ \\ell \\in L \\mid d(\\ell, r_0) > t \\} $$  \nand the set of **survivable laboratories**:  \n$$ T = \\{ \\ell \\in L \\mid d(\\ell, r_0) \\leq t \\} $$  \n\nA scientist starting at $ \\ell \\in L $ can reach $ \\ell' \\in L $ in time if $ d(\\ell, \\ell') \\leq t - d(\\ell', r_0) $.  \n\nThe problem reduces to:  \nFind a flow $ f: L \\times L \\to \\mathbb{Z}_{\\geq 0} $, where $ f(\\ell, \\ell') $ is the number of scientists moving from $ \\ell $ to $ \\ell' $, such that:  \n- $ \\sum_{\\ell' \\in L} f(\\ell, \\ell') \\leq s_\\ell $ for all $ \\ell \\in L $  \n- $ \\sum_{\\ell \\in L} f(\\ell, \\ell') \\leq c_{\\ell'} $ for all $ \\ell' \\in L $ with $ d(\\ell', r_0) \\leq t $  \n- $ \\sum_{\\ell \\in L} f(\\ell, \\ell') \\leq s_{\\ell'} $ for all $ \\ell' \\in S $ (scientists can stay in safe labs)  \n- For all $ \\ell, \\ell' \\in L $: if $ f(\\ell, \\ell') > 0 $, then $ d(\\ell, \\ell') \\leq t - d(\\ell', r_0) $  \n\nMaximize total saved scientists:  \n$$ \\sum_{\\ell' \\in L} \\min\\left( \\sum_{\\ell \\in L} f(\\ell, \\ell'),\\ c_{\\ell'} \\right) $$  \n\nThis is a **maximum flow problem** on a bipartite graph with capacities and distance constraints, or equivalently, a **transportation problem** with time-dependent reachability.","simple_statement":null,"has_page_source":false}