SP8583 NPOWM - Garden

瓦夏拥有一个非常美丽的乡村花园，这个花园是一个大小为 $n \times m$ 的矩形区域，被划分为 $n \cdot m$ 个方格。有一天，鲍勃想起需要在花园中选取的 $k$ 个重要位置之间修建一条路径，为此他打算在某些格子中铺上混凝土。 花园中的每个格子都有一个数值 $a_{ij}$，代表坐标为 $(i, j)$ 的格子中生长的花的数量。当铺设混凝土时，该格子中的所有花都会被摧毁。 鲍勃希望能够聪明地铺设混凝土，需满足以下条件： - 所有 $k$ 个重要的格子必须被混凝土覆盖。 - 任何两个重要格子之间必须存在一条由混凝土连接的路径，路径上的格子必须是相邻（共享边）的。 - 被摧毁的花的数量尽可能少。 由于花园面积较大，瓦夏请求你协助他完成这个任务。

第一行输入三个整数 $n, m, k$，分别表示花园的行数、列数和重要格子的数量（$1 \le n, m \le 100$，$1 \le k \le n \cdot m$）。接下来的 $n$ 行中，每行包含 $m$ 个整数 $a_{ij}$，表示每个格子中生长的花的数量（$1 \le a_{ij} \le 1000$）。接着的 $k$ 行中，每行包含两个整数 $x_i, y_i$，表示每个重要格子的坐标（$1 \le x_i \le n$，$1 \le y_i \le m$）。

第一行输出一个整数，表示在布置路径过程中被摧毁的花的最小数量。接下来输出 $n$ 行，每行用 $m$ 个字符描述花园的铺设方案，其中字符 `X` 表示已铺设混凝土的格子，而 `.` 表示未铺设的格子。如果存在多种方案，任选其一输出即可。 ### 示例 #### 输入 ``` 3 3 2 1 2 3 1 2 3 1 2 3 1 2 3 3 ``` #### 输出 ``` 9 .X. .X. .XX ``` **本翻译由 AI 自动生成**