- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در هر خانه از یک جدول \(n\) در \(m\) یک دومینوی ایستاده قرار داده شده است. هر دومینو یا عمودی است یا افقی (دومینوهای عمودی فقط در جهت بالا یا پایین میافتد و دومینوهای افقی فقط در جهت چپ یا راست). وقتی یک دومینو در یک جهت میافتد دومینوی موجود در خانهی بعدی (در همان جهت) نیز اگر از نظر عمودی و افقی بودن مانند این دومینو باشد میافتد (دومینوها فقط در شرایط گفته شده بر روی دومینوهای دیگر تاثیر میگذارند).
میخواهیم تعدادی دومینو را بیاندازیم به طوری که همهی دومینوها بیافتند. حداقل چند دومینو را باید بیاندازیم؟
ورودی
در خط اول ورودی دو عدد \( n \) و \( m \) آمده است که تعداد سطرها و ستونهای جدول را نشان میدهند.
در \( n \) خط بعدی در هر خط، \( m \) کاراکتر آمده که هر کدام نشان دهندهی وضعیت یک دومینو است (| برای دومینوهای افقی و - برای دومینوهای عمودی)
\[1 \le n, m \le 3000\]
خروجی
جواب مسئله را در یک خط چاپ کنید.
مثال
ورودی نمونه
3 3
|||
||-
||-
خروجی نمونه
4
در ورودی نمونه سه دومینوی واقع در ستون اول را به سمت راست و دومینوی واقع در ستون سوم و سطر دوم را به سمت پایین میاندازیم.