• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

تیمور که یکی از استف‌های زحمت‌کش مسابقات است عقیده دارد که از بین همه استف‌های عاشق مصطفی، مصطفی خودش عاشق استفی است که بتواند معماهای سخت را حل کند.

مصطفی معمایی طرح کرده و آن را برای همه استف‌ها فرستاده است تا آن را حل کنند.

او جدولی $m \times n$ برای استف‌ها فرستاده که هر خانه از آن x یا y است. استف‌ها می‌توانند در هر مرحله یک خانه از جدول را انتخاب کنند و محتوای‌ درون آن خانه را به x ، ‍y یا ‍‍z تبدیل کنند. استفی که بتواند در کمترین مراحل کاری کند که شرایط زیر برقرار باشد، این معما را حل کرده است.

۱- مسیری از یکی از خانه‌های سطر اول به یکی از خانه‌های سطر آخر وجود داشته باشد که خانه‌های آن فقط y و ‍z باشد.

۲- مسیری از یکی از خانه‌های ستون اول به یکی از خانه‌های ستون آخر موجود باشد که خانه‌های آن فقط x و ‍z باشد.

یک مسیر، دنباله‌ای از خانه‌های جدول است که در آن هر خانه به جز خانه آخر، با خانه بعدی‌اش مجاور ضلعی است.

از آنجایی که تیمور حوصله‌ی این سوسول بازی‌ها را ندارد از شما خواسته تا به او کمک کنید تا نظر مصطفی را جلب کند.

ورودی

در خط اول ابتدا عدد $n$ که تعداد سطر‌های جدول است و سپس عدد $m$ که تعداد ستون‌های جدول است به شما داده می‌شود.

در هر یک از $n$ خط بعدی، یک رشته‌ به طول $m$ از حروف x و y داده شده است.

$$ 1 \le n , m \le 1 \ 000$$

خروجی

در یک خط کمترین مراحل تغییر لازم برای برآورده کردن شرط‌های مصطفی را چاپ کنید.

مثال

ورودی نمونه ۱

2 2
xy
yx

خروجی نمونه ۱

2

ورودی نمونه ۲

3 5
xyxyy
yyyxy
yyyyx

خروجی نمونه ۲

3