Ksenia 有一个大小为 n × m 的棋盘。棋盘的每个单元格包含字符之一:“<”、“">”、“^”、“v”、“#”。包含字符“#”的单元格被阻止。我们知道所有接触边界的棋盘单元都被阻挡。
Ksenia 正在棋盘上玩两个棋子。最初,她将棋子放在棋盘上。当且仅当该单元格被阻挡时,棋盘的一个单元格可以包含两个棋子。在其他情况下,两个棋子不能站在一个牢房中。当克塞尼亚将棋子放在棋盘上时,游戏开始。在一次移动中,Ksenia 将每个 pawn 沿着相应 pawn 所在单元格上绘制的箭头方向移动到相邻单元格的一侧(如果 pawn 位于“#”上,则它不会移动)。假设 Ksenia 同时移动棋子(参见第二个测试用例)。
当然,Ksenia 是为了积分而战。如何计算每场比赛的得分?很简单!让我们数一下第一个棋子做了多少次动作,第二个棋子做了多少次动作,将这两个数字相加——这就是游戏的得分。
Ksenia 想知道:她能获得的最大分数是多少(为此,她应该在游戏早期将棋子放置在最佳位置)。帮助她找到那个号码。
输入
第一行包含两个整数,n 和 m (1 ≤ n, m ≤ 2000) — 棋盘的大小。接下来的 n 行每行包含 m 个字符——棋盘的描述。每个字符都是以下字符之一:“<”、“">”、“^”、“v”、“#”。
保证表格的边界单元格是阻塞单元格(带有字符“#”)。
输出
如果 Ksenia 可以获得无限多个点,则打印 -1。否则,打印她可以获得的最大分数。
示例
输入 #1
1 1 #
输出 #1
0
输入 #2
3 4 #### #>^# ####
输出 #2
3
输入 #3
3 4 #### #><# ####
输出 #3
-1
输入#4
7 5 ##### ##v## ##v## ##### ##^## ##^## #####
输出#4
4
输入 #5
7 5 ##### ##v## ##v## ##<## ##^## ##^## #####
输出 #5
5