У Васи есть очень красивый загородный сад, который представляет собой прямоугольное поле размером n × m, разделенное на n·m квадратных клеток. В один прекрасный день Вася вспомнил, что ему нужно проложить дорожки между k важными клетками с постройками — для этого он может залить бетоном некоторые из клеток своего сада.
Про каждую клетку сада известно число aij, которое означает количество цветов, растущих в клетке с координатами (i, j). При заливании бетоном все цветы, растущие в клетке, погибают.
Вася хочет залить бетоном некоторые клетки так, чтобы выполнялись условия:
- все k важных клеток обязательно должны быть залиты бетоном
- из каждой важной клетки до любой другой важной клетки существовал путь по залитым бетоном клеткам при условии, что соседними считаются клетки, имеющие общую сторону
- общее количество погибших растений должно быть минимально
Так как у Васи достаточно большой сад, то он просит Вас ему помочь.
Выходные данные
В первую строку выведите единственное целое число — минимальное количество погибших при строительстве растений. Далее выведите n строк по m символов в каждой — план сада, где символом «X» (заглавная латинская буква X) обозначайте залитую бетоном клеточку, а символом «.» (точка) — незалитую. Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3
|
9
.X.
.X.
.XX
|
|
2
|
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.
|