2. Toľko voľného miesta!

Povedali ste si niekedy po nástupe do autobusu: “Toľko voľného miesta! Prečo tu nie sú sedadlá?”. Nuž, časy, keď ste boli nútení stáť v poloprázdnom autobuse, budú už čoskoro minulosťou. Prichádza revolúcia v hromadnej doprave.

Na trhu sa totiž objavil superbus – autobus, v ktorom je každý centimeter štvorcový pokrytý čalúnenou sedačkou. Interiér superbusu obsahuje \(n\) radov a v každom z nich je \(m\) sedačiek vedľa seba. Navyše, sedačky nie sú všetky otočené dopredu. Aby si cestujúci mohli vybrať smer, ktorým sa chcú počas jazdy pozerať, v superbuse sú sedadlá pootáčané do každého zo 4 smerov.

Pri prvom testovaní superbusu sa ale zistilo, že má jednu fatálnu chybu – niektoré sedačky sú otočené čelom k sebe. A keď sú obe obsadené, niet miesta pre nohy cestujúcich.

Dizajnér superbusu preto potrebuje niektoré sedačky otočiť niekoľkokrát o deväťdesiat stupňov tak, aby žiadne dve sedačky neboli k sebe otočené čelom. Nakoľko už bolo vyrobených veľa superbusov, v každom z nich bude nutné tieto sedačky otočiť. To je veľa roboty – je preto žiadúce, aby bolo potrebné sedačky otáčať čo najmenejkrát.

Úloha

Na vstupe je mriežka, v ktorej je každé políčko – sedadlo – otočené na sever, východ, juh alebo na západ.

O mriežke hovoríme, že je v dobrom stave práve vtedy, keď žiadne dve susedné sedadlá nie sú natočené proti sebe.

V jednom kroku je povolené otočiť niektoré sedadlo o deväťdesiat stupňov doľava alebo doprava. Zistite, koľko najmenej krokov je potrebných na to, aby sme mriežku dostali do dobrého stavu.

Netradične vám k tejto úlohe naznačíme riešenie. Ak nápovedu nechcete vedieť, nepozerajte do poznámky pod čiarou. Ak si s úlohou neviete poradiť, možno vám poznámka pod čiarou¹ pomôže.

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(1 \leq n, m \leq 50\) – rozmery mriežky.

Nasleduje \(n\) riadkov, na každom z nich je \(m\) znakov popisujúcich natočenie danej sedačky. Znak ^ zodpovedá natočeniu na sever, > na východ, v na juh, a < na západ.

Formát výstupu

Na výstup vypíšte jedno celé číslo – najmenší počet krokov, na ktorý je možné dostať mriežku do dobrého stavu.

Príklad

Input:

3 3
>v<
>^<
^^^

Output:

2

Otočíme sedadlo v strede prvého riadku dvarát o 90 stupňov.

Input:

1 10
>>><<<>><<

Output:

2

Napríklad môžeme otočiť tretie sedadlo zľava a tretie sedladlo od konca smerom na sever.