CF382D.Ksenia and Pawns

Ksenia has a chessboard of size n × m. Each cell of the chessboard contains one of the characters: "<", ">", "^", "v", "#". The cells that contain character "#" are blocked. We know that all chessboard cells that touch the border are blocked.

Ksenia is playing with two pawns on this chessboard. Initially, she puts the pawns on the chessboard. One cell of the chessboard can contain two pawns if and only if the cell is blocked. In other cases two pawns can not stand in one cell. The game begins when Ksenia put pawns on the board. In one move, Ksenia moves each pawn to a side adjacent cell in the direction of arrows painted on the cell on which the corresponding pawn sits (if the pawn sits on "#", it does not move). Assume that Ksenia moves pawns simultaneously (see the second test case).

Of course, Ksenia plays for points. How can one calculate the points per game? Very simply! Let's count how many movements the first pawn made and how many movements the second pawn made, sum these two numbers — it will be the resulting score of the game.

Ksenia wonders: what is the maximum number of points she can earn (for that, she should place the pawns optimally well early in the game). Help her and find that number.

克谢尼娅有一个大小为 $n \times m$ 的棋盘。棋盘的每个格子中包含以下字符之一：“<”、“>”、“^”、“v”、“#”。其中，包含字符 “#” 的格子是被阻塞的。已知所有与棋盘边界相邻的格子均被阻塞。

克谢尼娅正在这个棋盘上用两个棋子进行游戏。初始时，她将这两个棋子放置在棋盘上。仅当某个格子被阻塞（即该格子含字符 “#”）时，该格子才可同时容纳两个棋子；其余情况下，一个格子最多只能容纳一个棋子。游戏从克谢尼娅将棋子放置到棋盘上时开始。在每一步中，克谢尼娅将每个棋子同时向其所在格子上所绘制的箭头所指方向移动一格（若棋子位于 “#” 格子上，则该棋子不移动）。注意：克谢尼娅是同时移动两个棋子的（参见第二个测试用例）。

当然，克谢尼娅的游戏目标是获得尽可能多的分数。那么，如何计算一局游戏的得分呢？非常简单！我们只需统计第一个棋子总共移动了多少步、第二个棋子总共移动了多少步，再将这两个数值相加——所得和即为该局游戏的最终得分。

克谢尼娅想知道：她最多能获得多少分？（为此，她必须在游戏初期以最优方式放置棋子。）请帮助她找出这个最大得分。

The first line contains two integers, n and m (1 ≤ n, m ≤ 2000) — the sizes of the board. Each of the following n lines contains m characters – the board's description. Each character is one of the characters: "<", ">", "^", "v", "#".

It is guaranteed that the border cells of the table are blocked cells (with character "#").

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2000$）——表示棋盘的尺寸。接下来的 $n$ 行，每行包含 $m$ 个字符，描述该棋盘。每个字符为以下字符之一："<"、">"、"^"、"v"、"#"。

保证表格的边界单元格均为障碍单元格（即字符为 "#"）。

If Ksenia can get infinitely many points, print -1. Otherwise, print the maximum number of points she can get.

如果克谢尼娅可以得到无限多的分数，则输出 -1；否则，输出她能得到的最高分数。