Будівництво басейну
Ви працюєте в міжнародній компанії з будівництва басейнів, яка спеціалізується на створенні плавальних зон. Новий клієнт бажає побудувати кілька нових зон басейнів.
Зона басейну являє собою прямокутну сітку розміром w×h квадратних ділянок, що можуть містити нуль або більше (можливо, роз'єднаних) басейнів. Басейн складається з однієї або кількох з'єднаних ділянок з ямами, які згодом будуть заповнені водою. Спочатку ви маєте ділянку землі, де кожна ділянка є або ямою ('.'), або рівною травою ('#'). Щоб перетворити цю землю на зону басейну, ви повинні дотримуватися наступних правил:
Ви можете залишити ділянку без змін. Це безкоштовно.
Якщо ділянка спочатку є травою, ви можете викопати там яму. Це коштує d євро.
Якщо ділянка спочатку є ямою, ви можете заповнити її і покласти траву зверху. Це коштує f євро.
Ви повинні встановити спеціальні елементи межі вздовж кожного краю, що розділяє остаточну ділянку з травою і остаточну ділянку з ямою, щоб запобігти витіканню води з басейну. Це коштує b євро за кожен елемент межі.
Найзовнішні рядки та стовпці зони басейну завжди повинні бути травою.
Ваше завдання — обчислити вартість найдешевшої можливої зони басейну, враховуючи планування існуючої ділянки землі.
Вхідні дані
На першому рядку задано позитивне ціле число: кількість тестових випадків, не більше 100. Далі для кожного тестового випадку:
один рядок з двома цілими числами w і h (2 ≤ w, h ≤ 50): ширина і висота будівельного майданчика.
один рядок з трьома цілими числами d, f і b (1 ≤ d, f, b ≤ 10000): вартість викопування нової ями, заповнення існуючої ями та встановлення елемента межі між басейном і ділянкою з травою.
h рядків по w символів кожен, що представляють планування оригінального будівельного майданчика.
Вихідні дані
Для кожного тестового випадку виведіть:
один рядок з цілим числом: вартість будівництва найдешевшої можливої зони басейну з оригінальної ділянки землі.