eolymp
bolt
Try our new interface for solving problems
Məsələlər

Живопись

Живопись

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

В стране Олимпия очень развита живопись. Картиной считается любой прямоугольник, который состоит из чёрных и белых единичных квадратов. Художник Олимпус решил радикально улучшить свои картины. Для этого он планирует к белому и чёрному цветам добавить ещё и серый оттенок. По его задумке, граница между каждыми чёрным и белым квадратом должна содержать серую линию, чтобы образовался эффект плавного перехода.

Однако перед началом работы, он обнаружил, что серая краска очень дорого стоит. Чтобы сэкономить деньги, художник решил оценить, не выгоднее ли сначала перекрасить некоторые белые квадраты в чёрные, а чёрные в белые, для того, чтобы минимизировать расходы на краску.

Напишите программу, которая по информации о существующей картине определяет минимальную сумму денег, которая понадобится на улучшение картины.

Giriş verilənləri

Первая строка содержит пять натуральных чисел: N, M (1 N, M 70) - высота и ширина картины, w, b, g (1 w, b, g 1000) - цена рисования одного белого единичного квадрата, чёрного единичного квадрата и серой линии единичной длины, соответственно. Далее следует N строк, каждая из которых состоит из M букв. Буква B соответствует чёрному квадрату, а W - белому.

Çıxış verilənləri

Вывести одно целое число, являющееся минимальной суммой затрат на улучшение картины.

Nümunə

Giriş verilənləri #1
3 2 10 12 1
BW
WB
BW
Çıxış verilənləri #1
7
Müəllif Vladimir Tkachuk
Mənbə 2007 XX All-Ukrainian Informatics Olympiad, Kremenchuk, April 10 - 16, Round 2