CF152E.Garden

Vasya has a very beautiful country garden that can be represented as an n × m rectangular field divided into n·m squares. One beautiful day Vasya remembered that he needs to pave roads between k important squares that contain buildings. To pave a road, he can cover some squares of his garden with concrete.

For each garden square we know number a__i__j that represents the number of flowers that grow in the square with coordinates (i, j). When a square is covered with concrete, all flowers that grow in the square die.

Vasya wants to cover some squares with concrete so that the following conditions were fulfilled:

• all k important squares should necessarily be covered with concrete
• from each important square there should be a way to any other important square. The way should go be paved with concrete-covered squares considering that neighboring squares are squares that have a common side
• the total number of dead plants should be minimum

As Vasya has a rather large garden, he asks you to help him.

瓦西娅拥有一座非常美丽的乡村花园，该花园可表示为一个 $n \times m$ 的矩形场地，被划分为 $n \cdot m$ 个方格。某一天，瓦西娅忽然想起他需要在包含建筑物的 $k$ 个重要方格之间铺设道路。为了铺设道路，他可以在花园的某些方格上浇筑混凝土。

对于每个花园方格，我们知道一个数值 $a_{ij}$，它表示坐标为 $(i,\,j)$ 的方格中生长的花朵数量。当某个方格被混凝土覆盖时，该方格中所有花朵都会死亡。

瓦西娅希望用混凝土覆盖一些方格，使得满足以下条件：

• 所有 $k$ 个重要方格必须被混凝土覆盖；
• 从任一重要方格出发，都应存在一条通往其他任意重要方格的路径；该路径必须完全由被混凝土覆盖的方格构成（相邻方格定义为具有公共边的方格）；
• 死亡的植物总数应最小。

由于瓦西娅的花园相当大，他请你来帮助他解决这个问题。

The first input line contains three integers n, m and k (1 ≤ n, m ≤ 100, n·m ≤ 200, 1 ≤ k ≤ min(n·m, 7)) — the garden's sizes and the number of the important squares. Each of the next n lines contains m numbers a__i__j (1 ≤ a__i__j ≤ 1000) — the numbers of flowers in the squares. Next k lines contain coordinates of important squares written as "x y" (without quotes) (1 ≤ x ≤ n, 1 ≤ y ≤ m). The numbers written on one line are separated by spaces. It is guaranteed that all k important squares have different coordinates.

第一行输入包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, m ≤ 100$，$n·m ≤ 200$，$1 ≤ k ≤ \min(n·m, 7)$），分别表示花园的尺寸以及重要方格的数量。接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{ij}$（$1 ≤ a_{ij} ≤ 1000$），表示各格子中花朵的数量。随后的 $k$ 行，每行以“$x$ $y$”（不含引号）的形式给出重要方格的坐标（$1 ≤ x ≤ n$，$1 ≤ y ≤ m$）。同一行中的数字以空格分隔。保证所有 $k$ 个重要方格的坐标互不相同。

In the first line print the single integer — the minimum number of plants that die during the road construction. Then print n lines each containing m characters — the garden's plan. In this plan use character "X" (uppercase Latin letter X) to represent a concrete-covered square and use character "." (dot) for a square that isn't covered with concrete. If there are multiple solutions, print any of them.

第一行输出一个整数——道路施工过程中死亡的植物的最小数量。然后输出 $n$ 行，每行包含 $m$ 个字符，表示花园的布局图。在该布局图中，用字符 "X"（大写拉丁字母 X）表示被混凝土覆盖的方格，用字符 "."（英文句点）表示未被混凝土覆盖的方格。若存在多种解法，输出任意一种即可。