Опасаясь приближения мирового экономического кризиса, государства Бермания, Беранция и Берталия заключили союз и разрешили жителям всех входящих в него государств беспрепятственный проход по территории любого из них. Дополнительно было решено построить дороги между государствами так, чтобы из любой точки любого государства можно было добраться до любой точки любого другого государства.

Так как дороги всегда обходятся недёшево, правительства государств новообразованного союза попросили вас помочь им оценить затраты. Для этого вам была выдана карта, которая представляет собой клетчатый прямоугольник из n строк по m клеток в каждой. Любая клетка карты либо принадлежит одному из трёх государств, либо является областью, на которой можно построить дорогу, либо является областью, на которой дорогу построить нельзя. Проходимыми являются все клетки, принадлежащие государствам, а также все клетки, в которых построены дороги. Из любой проходимой клетки можно перемещаться вверх, вниз, вправо и влево, если соответствующая такому перемещению клетка существует и является проходимой.

Требуется построить дороги в минимальном количестве клеток так, чтобы стало возможным добраться из любой клетки любого государства до любой клетки любого другого государства.

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