E. Сад
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

У Васи есть очень красивый загородный сад, который представляет собой прямоугольное поле размером n × m, разделенное на n·m квадратных клеток. В один прекрасный день Вася вспомнил, что ему нужно проложить дорожки между k важными клетками с постройками — для этого он может залить бетоном некоторые из клеток своего сада.

Про каждую клетку сада известно число aij, которое означает количество цветов, растущих в клетке с координатами (i, j). При заливании бетоном все цветы, растущие в клетке, погибают.

Вася хочет залить бетоном некоторые клетки так, чтобы выполнялись условия:

  • все k важных клеток обязательно должны быть залиты бетоном
  • из каждой важной клетки до любой другой важной клетки существовал путь по залитым бетоном клеткам при условии, что соседними считаются клетки, имеющие общую сторону
  • общее количество погибших растений должно быть минимально

Так как у Васи достаточно большой сад, то он просит Вас ему помочь.

Входные данные

В первой строке входных данных даны три целых числа n, m и k (1 ≤ n, m ≤ 100, n·m ≤ 200, 1 ≤ k ≤ min(n·m, 7)) — размеры сада и количество важных клеток. Далее в n строках по m чисел в каждой даны числа aij (1 ≤ aij ≤ 1000) — количество цветов в клетках. Далее в k строках даны координаты важных клеток в формате «x y» (без кавычек) (1 ≤ x ≤ n, 1 ≤ y ≤ m). Числа, расположенные в одной строке, разделены пробелами. Гарантируется, что все k важных клеток имеют различные координаты.

Выходные данные

В первую строку выведите единственное целое число — минимальное количество погибших при строительстве растений. Далее выведите n строк по m символов в каждой — план сада, где символом «X» (заглавная латинская буква X) обозначайте залитую бетоном клеточку, а символом «.» (точка) — незалитую. Если решений несколько, выведите любое.

Примеры
Входные данные
3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3
Выходные данные
9
.X.
.X.
.XX
Входные данные
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
Выходные данные
26
X..XX
XXXX.
X.X..
X.XX.