Вероника очень хорошо рисует и разукрашивает раскраски. Игорь и Ира купили ей новую пчелиную раскраску.
Раскраска состоит из $$$n$$$ строк, в каждой из которых ровно $$$m$$$ ячеек. Каждая ячейка является правильным шестиугольником, как соты у пчел и имеет не более 6 соседей. В качестве примера поле $$$5 \times 5$$$ выглядит следующим образом:
Изначально в раскраске какие-то ячейки уже покрашены. Вероника хочет закрасить минимальное количество ячеек так, чтобы получилась непрерывная линия из закрашенных ячеек, которая соединит первую строку с $$$n$$$-й строкой.
В первой строке содержатся два целых числа $$$n$$$, $$$m$$$ $$$(1 \leq n, m \leq 1000)$$$ — количество строк в раскраске и количество ячеек в каждой строке.
Далее заданы $$$n$$$ строк, в каждой строке ровно $$$m$$$ символов и каждая строка состоит только из символов «.» и «#». Символ «.» обозначает, что ячейка не закрашена, «#» — ячейка закрашена.
Выведите одно целое число – минимальное количество ячеек, которое необходимо закрасить, чтобы соединить первую строку с $$$n$$$-й строкой.
5 5....#.#....#......#..#...
2
