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

پروژه ساخت یک استخر به شما پیشنهاد شده و شما می‌خواهید این استخر را بسازید. «محوطه استخر» یک شبکه مستطیلی متشکل از $w \times h$ قطعه زمین مربعی است که از صفر یا تعدادی استخر (که ممکن است به هم متصل نباشند) تشکیل شده است. «استخر» تشکیل شده است از یک یا چند گودال متصل به هم، که بعدا از آب پر خواهد شد.

در ابتدا به شما یک تکه زمین داده می‌شود که هر قسمت از آن یا یک گودال (.) است و یا یک زمین چمن مسطح (#). به منظور تبدیل این زمین به استخر شما باید مطابق زیر عمل کنید:

• می‌توانید یک قسمت را به همان شکلی که هست رها کنید که هزینه‌ای برای شما ندارد.
• یک زمین چمن مسطح خاکبرداری کنید و یک گودال ایجاد کنید که هزینه آن $d$ چوق است.
• یک گودال را پر کنید و یک زمین چمن مسطح ایجاد کنید که هزینه آن $f$ چوق است.
• در مرز هر گودال و زمین چمن مسطح،‌ باید یک دیوار ایجاد شود تا آب استخر هدر نرود. هزینه ساخت دیوار بین هر دو قطعه مجاور زمین $b$ چوق است.
• قطعه زمین‌های مرزی «محوطه استخر» باید زمین چمن باشد.

شما باید به ارزان‌ترین شکل ممکن این «منطقه استخر» را با طرح داده شده از تکه زمین موجود بسازید.

ورودی

خط اول شامل یک عدد صحیح مثبت است که تعداد نمونه‌های ورودی را مشخص می‌کند.(حداکثر ۱۰۰ تا) سپس برای هر ورودی :

• یک خط شامل دو عدد صحیح $w,h$ ($2 \le w,h \le 50$) : عرض و طول زمین موردنظر برای ساخت.
• سه خط شامل سه عدد صحیح $d$، $f$ و $b$ ($1 \le d,f,b \le 10000$) : به ترتیب هزینه ایجاد یک گودال جدید، هزینه پرکردن یک گودال موجود و هزینه ساخت دیوار بین یک قطعه گودال و یک قطعه زمین چمن.
• در ادامه $h$ خط هر کدام شامل $w$ کاراکتر که طرح زمین اولیه را مشخص می کند.

خروجی

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

مثال

ورودی نمونه :

3
3 3
5 5 1
#.#
#.#
###
5 4
1 8 1
#..##
##.##
#.#.#
#####
2 2
27 11 11
#.
.#

خروجی نمونه :

9
27
22