برج‌سازی‌


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

عمو که فردی بسیار پول‌پرست است، به برج‌سازی روی آورده.

زمینی به عمو به ارث رسیده است و او میخواهد روی آن برج‌سازی کند. این زمین از بالا مانند جدولی با nn سطر و mm ستون دیده میشود که میتوان در خانه‌های آن برج ساخت. از قبل روی برخی از خانه های این جدول برج‌هایی نیمه‌کاره ساخته‌شده و عمو نمیتواند آن ها را خراب کند. همچنین بعلت خاک نامناسب، ساخت برج روی برخی از خانه های جدول امکان ندارد.

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

ورودی🔗

سطر اول ورودی شامل دو عدد nn و mm است که نمایانگر تعداد سطر ها و تعداد ستون های جدول هستند. سپس در هریک از nn سطر بعدی، یک رشته به طول mm متشکل از یکی از سه کاراکتر . یا # و یا ? آمده است که به ترتیب نمایانگر خانه‌ی با خاک نامرغوب، خانه‌ی با برج نیمه‌کاره و خانه‌ی با توانایی ساخت برج هستند.

1n,m501 \le n, m \le 50

خروجی🔗

در تنها سطر خروجی یک عدد چاپ کنید که برابر بیشترین سود ممکن برای عمو است.

مثال🔗

ورودی نمونه ۱🔗

3 3
.?.
.?.
.#.
Plain text

خروجی نمونه ۱🔗

8
Plain text

ورودی نمونه ۲🔗

5 8
.#...##.
.##..?..
.###.#.#
??#..?..
###?#...
Plain text

خروجی نمونه ۲🔗

42
Plain text