[Wc2008]游览计划

给定一个由 $N$ 行 $M$ 列方格组成的区域。输入值为 $0$ 的方格是景点，其余方格中的数值表示控制该方格至少需要安排的志愿者人数。

你可以选择若干非景点方格，并在其中安排相应数量的志愿者。方格之间仅按上、下、左、右 $4$ 个方向相邻。要求所有景点位于同一个连通区域中，即任意两个景点之间都能只经过景点或被选择的方格互相到达。

请最小化所选择方格需要的志愿者人数之和，并输出这个最小值以及一个达到最小值的方案。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示方格区域的行数和列数。

接下来 $N$ 行，每行包含 $M$ 个非负整数。若某个整数为 $0$，则对应方格是景点；否则，该整数表示控制对应方格至少需要的志愿者人数。

相邻整数之间由一个或多个空格分隔，行首和行末也可能存在多余的空格。

输出格式

输出共 $N+1$ 行。

第一行输出一个整数，表示使所有景点连通所需安排的最少志愿者总数。

接下来 $N$ 行，每行输出 $M$ 个字符，描述方案中对应方格的状态：

• _ 表示该非景点方格没有安排志愿者；
• o 表示该非景点方格安排了志愿者，并贡献输入中该方格给出的志愿者人数；
• x 表示该方格是景点，所有景点都必须标记为 x。

输出的方案必须使所有景点能够通过景点或标记为 o 的方格，沿上、下、左、右 $4$ 个方向互相到达，并且安排的志愿者总数达到全局最小值。

请严格遵守输出格式。不能缺少任何一行，每行的字符数必须符合要求，并且行中不允许出现多余的空格。

样例输入

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

样例输出

6
xoox
___o
___o
xoox

数据范围

• 对于 $100\%$ 的数据，$N,M,K\le 10$，其中 $K$ 为景点的数量；
• 输入中的所有整数均在区间 $[0,2^{16}]$ 内。

来源与许可

本题为 WC 2008 试题「游览计划」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 4
0 1 1 0
2 5 5 1
1 5 5 1
0 1 1 0

输出

6
xoox
___o
___o
xoox