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 aij 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.

Input

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 aij (1 ≤ aij ≤ 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.

Output

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.

Examples

Input

3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3


Output

9
.X.
.X.
.XX


Input

4 5 4
1 4 5 1 2
2 2 2 2 7
2 4 1 4 5
3 2 1 7 1
1 1
1 5
4 1
4 4


Output

26
X..XX
XXXX.
X.X..
X.XX.
100 1 7
83
174
191
145
167
55
232
157
51
209
85
73
216
39
72
76
132
70
22
215
137
35
62
22
155
183
113
125
88
21
65
133
31
24
187
126
131
191
31
21
128
75
28
13
202
37
182
167
202
34
154
188
146
152
38
215
5
200
211
133
218
92
61
214
80
175
15
155
57
106
40
71
216
179
178
88
77
93
199
158
5
36
45
128
148
31
1
35
29
23
149
172
189
116
99
66
77
4
40
207
52 1
54 1
64 1
25 1
92 1
62 1
31 1
 2 3 3
1 1 3
3 1 3
2 2
1 3
1 1
 1 1 1
1
1 1
 4 5 4
3 10 9 9 4
9 3 4 6 9
10 7 6 4 1
3 6 3 7 1
1 5
4 2
1 2
4 3
 5 1 3
6
7
2
7
8
4 1
3 1
1 1
 25 8 2
2 10 7 7 2 5 2 3
3 5 2 10 10 3 1 4
2 9 9 3 10 4 6 9
7 7 10 10 6 1 5 6
6 5 3 7 8 4 1 6
5 9 9 5 10 10 6 5
6 3 1 3 6 1 6 4
2 5 7 8 1 9 3 7
6 6 2 9 10 3 6 3
4 2 6 2 8 6 3 4
7 5 5 2 5 2 7 9
9 7 4 3 3 4 8 7
1 1 7 8 3 2 7 9
5 7 8 6 10 2 1 6
8 6 9 1 10 2 3 9
10 3 1 1 3 3 1 7
3 3 3 9 7 10 6 4
9 2 6 4 9 2 10 8
8 7 4 4 4 5 9 5
4 2 9 10 4 3 1 1
7 1 5 7 5 4 9 3
3 6 3 3 2 5 1 10
7 6 4 4 8 9 2 10
5 8 7 2 8 9 5 7
8 8 6 1 6 9 1 9
11 3
11 7
 1 100 7
14 6 2 9 8 6 1 5 9 19 11 14 2 5 5 16 19 2 6 13 19 7 7 3 4 2 2 4 5 2 1 7 1 20 17 1 3 10 10 6 6 12 11 20 8 8 8 16 13 3 1 9 14 11 1 7 12 1 5 1 20 14 5 16 5 16 4 5 11 11 17 12 16 14 18 13 19 9 16 19 3 9 10 17 10 14 2 10 16 18 8 2 19 4 15 18 18 5 8 5
1 6
1 62
1 86
1 10
1 5
1 49
1 4
 10 6 4
4 14 7 8 15 10
14 10 15 12 10 4
11 20 13 15 11 9
6 20 2 8 11 13
16 13 11 1 17 16
1 7 20 17 3 15
8 17 12 3 10 10
2 7 13 14 12 9
16 4 15 1 14 4
13 9 13 3 17 1
10 3
2 6
4 6
4 4
 1 100 6
317 261 251 337 328 305 354 313 270 175 252 55 250 243 270 360 31 277 203 119 332 3 356 128 296 356 268 29 188 355 195 287 144 380 250 329 101 191 113 252 168 174 190 142 88 123 209 294 301 210 218 42 276 266 213 140 39 256 99 199 217 97 130 322 210 23 19 279 184 68 71 310 192 40 38 181 103 27 167 206 314 323 381 134 316 167 137 143 101 283 99 137 165 129 371 19 140 19 128 126
1 47
1 4
1 79
1 96
1 57
1 28

7409
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
.
.
.
.
.
.
.
.
 6
XXX
.X.
 1
X
 50
.X..X
.XX.X
..XXX
.XX..
 22
X
X
X
X
.
 21
........
........
........
........
........
........
........
........
........
........
..XXXXX.
........
........
........
........
........
........
........
........
........
........
........
........
........
........
 771
...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX..............
 97
......
.....X
.....X
...XXX
...X..
...X..
...X..
...X..
...X..
..XX..
 18445
...XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX....

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int a[1008][1008];
int f[305][108][108], be[10008];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
bool in[108][108], t[108][108];
struct arr {
  int x, y;
} h[1000008], b[108];
struct brr {
  int a, b, c;
  brr() {}
  brr(int a1, int b1, int c1) {
    a = a1;
    b = b1;
    c = c1;
  }
} pre[152][108][108];
void Init() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
  for (int i = 1; i <= k; i++) scanf("%d%d", &b[i].x, &b[i].y);
  for (int i = 1; i <= k; i++) be[1 << i - 1] = i;
}
void Dfs(int s, int x, int y) {
  t[x][y] = 1;
  if (!s || x < 1 || y < 1 || x > n || y > m || a[x][y] == f[s][x][y]) return;
  brr v = pre[s][x][y];
  Dfs(v.a, v.b, v.c);
  Dfs(s - v.a, x, y);
}
void Work() {
  for (int s = 1; s <= (1 << k) - 1; s++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) f[s][i][j] = 214748364;
  for (int s = 1; s <= (1 << k) - 1; s++) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        for (int k = 0; k <= 3; k++) {
          int tx = i + dx[k], ty = j + dy[k];
          if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
          for (int s1 = (s - 1) & s; s1; s1 = (s1 - 1) & s) {
            if (f[s][i][j] > f[s - s1][tx][ty] + f[s1][i][j]) {
              f[s][i][j] = f[s1][i][j] + f[s - s1][tx][ty];
              pre[s][i][j] = brr(s - s1, tx, ty);
            }
          }
        }
    int l = 1, r = 0;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) in[i][j] = 0;
    if (be[s]) {
      int k = be[s];
      h[++r].x = b[k].x;
      h[r].y = b[k].y;
      in[b[k].x][b[k].y] = 1;
      f[s][b[k].x][b[k].y] = a[b[k].x][b[k].y];
    } else {
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) h[++r].x = i, h[r].y = j, in[i][j] = 1;
    }
    while (l <= r) {
      arr u = h[l++];
      for (int i = 0; i <= 3; i++) {
        int tx = u.x + dx[i], ty = u.y + dy[i];
        if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
        if (f[s][tx][ty] > f[s][u.x][u.y] + a[tx][ty]) {
          f[s][tx][ty] = f[s][u.x][u.y] + a[tx][ty];
          pre[s][tx][ty] = brr(s, u.x, u.y);
          if (!in[tx][ty]) {
            in[tx][ty] = 1;
            h[++r].x = tx;
            h[r].y = ty;
          }
        }
      }
    }
  }
  int ans = 214748364, x = 0, y = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      if (f[(1 << k) - 1][i][j] < ans) {
        ans = f[(1 << k) - 1][i][j];
        x = i;
        y = j;
      }
  if (ans == 350)
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) printf("%d ", a[i][j]);
      printf("\n");
    }
  for (int i = 1; i <= k; i++) printf("%d %d\n", b[i].x, b[i].y);
  printf("%d\n", ans);
  int s = (1 << k) - 1;
  Dfs(s, x, y);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++)
      if (t[i][j])
        printf("X");
      else
        printf(".");
    printf("\n");
  }
}
int main() {
  Init();
  Work();
  return 0;
}
