Mahjong este un joc originar din China, devenit foarte cunoscut datorită numeroaselor sale versiuni care circulă pe Internet. În această problemă, propunem o variantă simplificată, pentru un singur jucător.
Tabla de joc este dreptunghiulară, împărţită în NxM celule. În fiecare celulă se poate afla un singur jeton. Jetoanele sunt colorate în N*M/2 culori (numerotate de la 1 la N*M/2). Iniţial pe tablă se află exact două jetoane din fiecare culoare. La o mutare un jucător poate elimina de pe tablă două jetoane de aceeaşi culoare, cu condiţia ca cele două jetoane să fie ambele extremităţi de acelaşi tip.
Există 4 tipuri de extremităţi: extremitate stânga (cel mai din stânga jeton de pe linia sa); extremitate dreapta (cel mai din dreapta jeton de pe linia sa); extremitate sus (cel mai de sus jeton de pe coloana sa) şi extremitate jos (cel mai de jos jeton de pe coloana sa).
Scopul jocului este să elimini de pe tablă cât mai multe jetoane.
Cerinţă
Dată fiind configuraţia de joc iniţială, să se determine numărul maxim de mutări care pot fi executate.
Date de intrare
Fişierul de intrare mahjong.in conţine pe prima linie două numere naturale N M, separate prin spaţiu. Pe fiecare dintre următoarele N linii se află câte M numere naturale separate prin spaţiu (al j-lea număr de pe linia i se află culoarea jetonului plasat în celula de pe linia i şi coloana j pe tabla de joc).
Date de ieşire
Fişierul de ieşire mahjong.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de mutări ce pot fi efectuate.
Restricţii
0 < N, M ≤ 300
N*M este număr par.
Exemple
mahjong.in
mahjong.out
Explicatie
4 4
4 1 3 6
5 2 5 2
4 7 3 8
1 6 7 8
3
Se pot executa 3 mutări: se elimină jetoanele de culoare 4, 1, 8.