Задача G. РЛС ≡

Условие

Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более 5). К сожалению, их нельзя ставить рядом — они друг для друга создают помехи. Каждый передатчик состоит из квадратных модулей, которые располагаются вплотную друг к другу.

Вам дана карта района, в котором расположена РЛС. Вся карта для удобства разбита на квадраты, и для каждого квадрата известно, располагается в нем какой-то из модулей одного из передатчиков РЛС или нет.

Требуется оградить забором (или несколькими заборами) минимально возможной суммарной длины все передатчики РЛС. Забор — это произвольная ломаная (ее элементы не обязаны идти по сторонам клеток). Одним забором могут быть огорожены сразу несколько передатчиков.

В примере на рисунке РЛС состоит из 5 передатчиков. Длина забора вокруг передатчика 1 равна 9.236. Передатчики 2 и 3 окружены общим забором длины 6.828, и передатчики 4 и 5 окружены общим забором длины 10.828.

Формат входного файла

Во входном файле записаны два числа N и M, задающие размеры района, в котором расположена РЛС (1 \le N \le 20, 1 \le M \le 20). Далее идет N строк, по M чисел в каждой, задающих карту района. Каждое из этих чисел 0 или 1 — 1 означает, что в этом квадрате находится один из модулей передатчика РЛС, а 0 - что в этом квадрате ничего ценного нет.

Общее количество передатчиков РЛС не превышает 5. Каждый передатчик - это связанная группа модулей (модули называются связанными, если они располагаются в квадратах карты, у которых есть общая граница, либо связаны через какие-то другие модули).

Ограничения на число модулей нет.

Формат выходного файла

В выходной файл выведите одно число - минимально возможную длину забора с тремя значащими цифрами после точки.

Примеры тестов

9 10
0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 0
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0

26.893

3 3
0 0 0
0 1 0
0 0 0

4.000