Живопис#4351
У країні Олімпія дуже цінується мистецтво живопису. Картину визначають як будь-який прямокутник, що складається з білих і чорних одиничних квадратів. Художник Олімп вирішив удосконалити свої картини, ввівши між чорним і білим кольорами сірий відтінок. Його ідея полягає в тому, щоб додати сіру лінію по межі кожного чорного і білого квадрата, створюючи ефект плавного переходу.
Однак перед початком роботи Олімп зрозумів, що сіра фарба досить дорога. Щоб зекономити, він розглянув можливість перефарбувати деякі білі квадрати в чорний та навпаки, з метою мінімізувати загальні витрати на фарбу.
Ваше завдання — написати програму, яка, маючи опис поточної картини, визначить мінімальні витрати, необхідні для її удосконалення.
Перший рядок містить п’ять натуральних чисел: , (1 \le N, M \le 70) — висота й ширина картини, та , , (1 \le w, b, g \le 1000) — вартість фарбування одного білого квадрата, одного чорного квадрата та сірої лінії одиничної довжини відповідно. Далі йдуть рядків по символів у кожному, де символ означає чорний квадрат, а — білий квадрат.
Виведіть одне ціле число — мінімальні витрати, необхідні для удосконалення картини.
Приклад 1