Рабочее место участника

Несколько клонов находятся на поле размером `N\ times\ M`, на котором есть некоторое количество препятствий. Клонам необходимо переместиться в новые позиции. Все клоны могут двигаться одновременно, но в каждой клетке может находиться только один клон. Раз в секунду каждый клон может либо перейти в соседнюю клетку, имеющую общую сторону с клеткой, на которой он находится, либо остаться на месте.

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

Первая строка содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 15`) – размеры поля. Далее следует `N` строк, содержащих по `M` символов. Символ '#' обозначает клетку с препятствием, '.' – пустую клетку, 'S' – начальную позицию какого-либо клона, 'E' – пустую клетку, конечную позицию для клона. Гарантируется, что клоны могут пройти от начальной позиции до конечной (все связные области содержат одинаковое количество символов 'S' и 'E').

Вывести в первой строке два целых числа, разделенных пробелом – минимальное количество секунд для изменения расположения клонов и минимальная суммарное расстояние, пройденное при этом клонами.

3 3
S#.
S..
#EE

3 6

3 5
SSSSS
##.##
EEEEE

6 22