D. Ксюша и пешки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Ксюши есть шахматная доска размером n × m. На каждой клетке этой шахматной доски нарисован один из символов: «<», «>», «^», «v», «#». Клетки, на которых нарисован символ «#», Ксюша называет заблокированными. Известно, что все клетки шахматной доски, которые касаются ее границы, являются заблокированными.

Ксюша играет с двумя пешками на этой шахматной доске. Изначально она ставит пешки на шахматную доску. Причем в одной клетке шахматной доски в один момент времени могут стоять две пешки тогда и только тогда, когда эта клетка заблокированная. В других случаях две пешки не могут находиться в одной клетке. Игра начинается, когда Ксюша поставила пешки на доску. За один ход Ксюша перемещает каждую из пешек на соседнюю по стороне клетку в направлении стрелки, нарисованной на клетке, на которой стоит соответствующая пешка (если пешка стоит на «#», она не двигается). Считайте, что Ксюша двигает пешки одновременно (смотрите второй тестовый пример).

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

Ксюше очень интересно, какое максимальное количество очков она может заработать (для этого одна должна оптимально разместить пешки в самом начале игры). Помогите ей, найдите это число.

Входные данные

В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 2000) — размеры доски. В каждой из следующих n строк записано по m символов — описание доски. Каждый символ — это один из символов: «<», «>», «^», «v», «#».

Гарантируется, что граничные клетки доски — это заблокированные клетки (с символом «#»).

Выходные данные

Если Ксюша может заработать бесконечно большое количество очков, выведите -1. Иначе выведите максимальное количество очков, которое она может заработать.

Примеры
Входные данные
1 1
#
Выходные данные
0
Входные данные
3 4
####
#>^#
####
Выходные данные
3
Входные данные
3 4
####
#><#
####
Выходные данные
-1
Входные данные
7 5
#####
##v##
##v##
#####
##^##
##^##
#####
Выходные данные
4
Входные данные
7 5
#####
##v##
##v##
##<##
##^##
##^##
#####
Выходные данные
5