Строительство бассейна
Вы работаете в Международной компании по строительству бассейнов, которая специализируется на создании зон для плавания. Новый клиент хочет построить несколько новых зон бассейнов.
Зона бассейна представляет собой прямоугольную сетку размером w×h квадратных участков, состоящую из нуля или более (возможно, несвязанных) бассейнов. Бассейн состоит из одного или нескольких соединенных участков с ямами, которые позже будут заполнены водой. Изначально у вас есть участок земли, где каждый участок либо яма в земле ('.'), либо ровная трава ('#'). Чтобы преобразовать эту землю в зону бассейна, вы должны соблюдать следующие правила:
Вы можете оставить участок как есть. Это ничего не стоит.
Если участок изначально покрыт травой, вы можете выкопать там яму. Это стоит d евро.
Если участок изначально является ямой, вы можете засыпать яму и положить сверху траву. Это стоит f евро.
Вы должны разместить специальные пограничные элементы вдоль каждого края, проходящего между конечным участком с травой и конечным участком с ямой, чтобы вода не вытекала из бассейна. Это стоит b евро за каждый пограничный элемент.
Самые внешние ряды и столбцы зоны бассейна всегда должны быть покрыты травой.
Вам поручено рассчитать стоимость самого дешевого возможного варианта зоны бассейна, учитывая планировку существующего участка земли.
Входные данные
На первой строке указано положительное целое число: количество тестовых случаев, не более 100. После этого для каждого тестового случая:
одна строка с двумя целыми числами w и h (2 ≤ w, h ≤ 50): ширина и высота строительного участка.
одна строка с тремя целыми числами d, f и b (1 ≤ d, f, b ≤ 10000): стоимость выкапывания новой ямы, засыпки существующей ямы и строительства пограничного элемента между бассейном и участком с травой.
h строк по w символов каждая, обозначающих планировку оригинального строительного участка.
Выходные данные
Для каждого тестового случая:
одна строка с целым числом: стоимость строительства самого дешевого возможного варианта зоны бассейна из оригинального участка земли.