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