P4294 [WC2008] 游览计划

UPD： - @panda_2134 提供 Special Judge； - @yzy1 提供了[两组 hack 数据](https://www.luogu.com.cn/discuss/527294)，即不算分的 subtask1； - @kradcigam [完善](https://www.luogu.com.cn/discuss/873182)了 Special Judge。

从未来过绍兴的小 D 有幸参加了 Winter Camp 2008，他被这座历史名城的秀丽风景所吸引，强烈要求游览绍兴及其周边的所有景点。 主办者将绍兴划分为 $N$ 行 $M$ 列 $(N×M)$ 个分块，如下图（$8\times8$）：  景点含于方块内，且一个方块至多有一个景点。无景点的方块视为路。 为了保证安全与便利，主办方依据路况和治安状况，在非景点的一些方块内安排不同数量的志愿者；在景点内聘请导游（导游不是志愿者）。在选择旅游方案时，保证任意两个景点之间，存在一条路径，在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要，又能够让志愿者的总数最少。 例如，在上面的例子中，在每个没有景点的方块中填入一个数字，表示控制该方块最少需要的志愿者数目：  图中用深色标出的方块区域就是一种可行的志愿者安排方案，一共需要 $20$ 名志愿者。由图可见，两个相邻的景点是直接（有景点内的路）连通的（如沈园和八字桥）。 现在，希望你能够帮助主办方找到一种最好的安排方案。

第一行有两个整数，$N$ 和 $M$，描述方块的数目。 接下来 $N$ 行，每行有 $M$ 个非负整数，如果该整数为 $0$，则该方块为一个景点；否则表示控制该方块至少需要的志愿者数目。相邻的整数用（若干个）空格隔开，行首行末也可能有多余的空格。

由 $N+1$ 行组成。第一行为一个整数，表示你所给出的方案中安排的志愿者总数目。 接下来 $N$ 行，每行 $M$ 个字符，描述方案中相应方块的情况： - `_`（下划线）表示该方块没有安排志愿者； - `o`（小写英文字母 o）表示该方块安排了志愿者； - `x`（小写英文字母 x）表示该方块是一个景点； 注：请注意输出格式要求，如果缺少某一行或者某一行的字符数目和要求不一致（任何一行中，多余的空格都不允许出现），都可能导致该测试点不得分。

所有的 $10$ 组数据中 $N,M$，以及景点数 $K$ 的范围规定如下： ::cute-table{tuack} |测试点编号| $N$ | $M$ | $K$ | |:-:|:-:|:-:|:-:| | 1|$\le 2$|$\le 2$|$\le 2$| | 2|$\le 4$|$\le 5$|$\le 4$| | 3|$\le 2$|$\le 10$|$\le 3$| | 4|$\le 6$|$\le 7$|$\le 5$| | 5|$\le 8$|$\le 9$|$\le 7$| | 6|$\le 10$|$\le 9$|$\le 10$| | 7|$\le 9$|$\le 10$|$\le 10$| | 8|$\le 10$|$\le 10$|$\le 3$| | 9|$\le 10$|$\le 10$|$\le 10$| |10|$\le 10$|$\le 10$|$\le 10$|  输入文件中的所有整数均不小于 $0$ 且不超过 $2^{16}$。