Problem description
Powszechnie wiadomo, że pola szachownicy pomalowane są na dwa różne kolory, w taki sposób, że każde dwa pola stykające się bokiem mają różne kolory. Jasio na wysypisku śmieci znalazł coś co przypomina szachownicę. Jest prostokątne, ma pola, każde z nich pomalowane jest na jeden kolor, ale niekoniecznie użyto dokładnie dwóch kolorów, niekoniecznie też każde dwa sąsiednie pola mają różne kolory. Ile najmniej pól Jasio musi przemalować, żeby otrzymać sensowną szachownicę? Jasio nie jest wybredny, nie jest dla niego bardzo istotne jakie konkretnie kolory pozostaną.
Napisz program, który: wczyta obecny stan znalezionej planszy, wyznaczy minimalną liczbę pól, którym należy zmienić kolor, żeby stała się szachownicą i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i określające kolejno: wysokość i szerokość planszy. W kolejnych N wierszach znajduje się po M znaków – małych liter alfabetu angielskiego, określających kolory pól.
Wyjście
W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowitą – minimalną liczbę pól, którym należy zmienić kolor, aby uzyskać szachownicę.
Ograniczenia
2 ≤ N, M ≤ 1 000.
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Pole |