Острова
Чтобы не отставать от современной мировой тенденции, правительство страны Олимпия планирует построить несколько островов для привлечения туристов. Карта островов уже подготовлена и представляет собой таблицу размером N x M клеток. Каждая клетка может быть водой или сушей. Набор клеток, которые представляют сушу, есть островом, когда из любой из них можно попасть в любую другую, перемещаясь по соседним по горизонтали или вертикали клеткам, и не существует других таких клеток вне набора.
Для удобства было решено построить мосты между некоторыми островами так, чтобы все острова стали связанными между собой. Мосты должны строиться только по вертикали или горизонтали, проходить только по клеткам с водой, начинаться и заканчиваться клетками с сушей. За стоимость строительства моста можно считать количество клеток воды, через которые он проходит. Требуется найти минимальную возможную общую стоимость строительства группы мостов, которые связывали бы между собой все острова. Другими словами, чтобы из каждой клетки суши можно было достичь любой другой, перемещаясь по соседним по вертикали и горизонтали клеткам суши, либо мостам. Два разных моста могут пересекаться между собой, т.е. проходить через одну и ту же самую клетку воды на разных уровнях.
Напишите программу, которая по карте островов находит минимальную стоимость строительства группы мостов, которые соединяют все острова.
Входные данные
Первая строка содержит два целых числа N и M (1 ≤ N, M ≤ 500) - размеры карты островов. Каждая из последующих N строк содержит M символов 0 (вода) либо 1 (суша).
Выходные данные
Вывести одно целое число - найденную минимальную стоимость строительства мостов. Если соединить острова мостами невозможно, вывести число -1.