F. Flujo mínimo
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Según la mitología azteca, el camino al inframundo, Mictlán, es un arduo viaje de nueve niveles. Antonia ha llegado a uno de estos laberintos, un lugar donde las almas de los difuntos son guiadas por las corrientes del viento, que soplan en una de cuatro direcciones: arriba (^), abajo (v), izquierda (<) o derecha (>).

El laberinto es una cuadrícula de R × C celdas. Para llegar a su destino, Antonia debe ir de la celda de entrada (0, 0) a la celda de salida (R−1, C−1).

Moverse a través del laberinto tiene un costo de energía. Si se mueve a una celda adyacente (arriba, abajo, izquierda, o derecha) a favor de la corriente del viento de la celda actual, el costo es 0. ¡El viento la empuja! Si se mueve a una celda adyacente en contra de la corriente del viento, el costo es 1. ¡Debe usar su propia fuerza para avanzar!

La misión de Antonia es encontrar el mínimo costo de energía para llegar del punto de partida al punto final, ayuda a Antonia en esta díficil misión.

Input

La primera línea contiene dos enteros R y C (1 ≤ R, C ≤ 500), las dimensiones de la cuadrícula. Las siguientes R líneas contienen una cadena de C caracteres, cada uno representando la dirección del viento (^, v, <, >).

Output

Un solo entero, el mínimo costo de energía necesaria para ir de inicio a fin.

Examples
Input
4 5
>>>><
^v>><
^<>v>
<v>><
Output
2
Input
2 2
<>
^v
Output
2