2. Ako to len ofarbiť

Miška veľmi rada vymýšľa. Prednedávnom si chcela zaobstarať novú malú mačku a jej priateľ musel vynaložiť všetky svoje sily na to, aby ju prehovoril, že je to hlúposť. Teraz si vymyslela, že sa jej nepáči, ako vyzerá jej terasa.

Miškina terasa sa skladá z \(N \times M\) rovnako veľkých štvorcových kachličiek, ktoré tvoria obdĺžnik. Aktuálne majú všetky kachličky jednu z dvoch farieb - ružovú alebo fialovú. Miška je s farbami spokojná, chce však, aby jej terasa vyzerala trocha inak. Chce, aby sa žiadne dve kachličky s rovnakou farbou nedotýkali hranou (rohom môžu). Keďže hádať sa s Miškou je ťažšie než jednoducho premaľovať terasu, Miškin priateľ by rád vedel, koľko najmenej kachličiek treba premaľovať, aby bola Miška spokojná.

Formát vstupu

V prvom riadku vstupu dostanete dve čísla \(n\) (\(1 \leq n \leq 10^6\)) - výšku terasy, a \(m\) (\(1 \leq m \leq 10^6\)) - šírku terasy.

Nasleduje \(n\) riadkov. V každom riadku je reťazec dĺžky \(m\) pozostávajúci z písmeniek \(r\) (ružová kachlička) alebo \(f\) (fialová kachlička).

V sadách platia nasledujúce obmedzenia:

Formát výstupu

Na jeden riadok vypíšte jedno číslo - koľko najmenej kachličiek musíme premaľovať tak, aby sa žiadne dve kachličky rovnakej farby nedotýkali hranou.

Príklad

Input:

1 1
r

Output:

0

Tu netreba prefarbovať žiadnu kachličku.

Input:

2 3
rfr
frf

Output:

0

Taktiež nemusíme nič prefarbovať.

Input:

2 2
rf
rr

Output:

1

Potrebujeme prefarbiť ľavé dolné políčko na fialové, čo je jedno prefarbenie.