Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача D. Оптом дешевле

Задачу добавил: alef

Успешно сдано решений: 67

Ограничение по времени: 2 с на тест

Ограничение по памяти: 256 Мб

Поскольку погода устроителей так и продолжает не радовать, они планируют использовать рулонный газон. 

Дорожка для забега на роликах имеет длину n метров. Устроители очень тщательно готовятся к чемпионату, поэтому они поделили её на участки длиной 1 метр и для каждого такого участка провели исследование почвы. Оказалось, что придётся использовать два вида газона. Для определённости будем называть их A и B.

Компания, которая будет выполнять работы, укладывает один метр газона вида A за p1 денежных единиц, а один метр газона вида B за p2 денежных единиц. Однако если заказать укладку d1 или более метров газона вида A подряд, то один метр обойдётся немного дешевле: s1 денежных единиц. Для газона вида B тоже есть оптовая скидка: если заказать укладку d2 или более метров этого газона подряд, то один метр будет стоить s2 денежных единиц. 

Устроители располагают картой дорожки для забега, на которой каждый участок помечен символом A, если на нём допустимо использовать только газон вида A, символом B, если допустимо использовать только газон вида B, и символом 0, если можно использовать как газон вида A, так и газон вида B.

Ваша задача — определить минимальную стоимость работ по покрытию дорожки газоном.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 105) — длина дорожки для забега.

Во второй строке содержится n символов A (заглавная латинская буква), B (заглавная латинская буква), 0 (ноль), означающих, какой вид газона можно использовать для данного участка.

В третьей строке содержатся целые числа p1d1s1 (1 ≤ s1 < p1 ≤ 105,  2 ≤ d1 ≤ 105), описанные в условии задачи.

В четвёртой строке содержатся целые числа p2d2s2 (1 ≤ s2 < p2 ≤ 105,  2 ≤ d2 ≤ 105), описанные в условии задачи.

Выходные данные

В первой строке выведите минимально возможную стоимость покрытия дорожки газоном.

Во второй строке выведите карту дорожки, в которой символы 0 заменены на символы A или B в зависимости от выбора типа газона.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач пройдены.

Подзадача 1 (до 20 баллов)

1 ≤ n ≤ 15

Подзадача 2 (до 20 баллов)

1 ≤ n ≤ 103

Необходимые подзадачи: 1

Подзадача 3 (до 60 баллов)

1 ≤ n ≤ 105

Необходимые подзадачи: 1, 2

По запросу сообщается номер первого непройденного теста.

Примеры

входные данные
10
AB000A00B0
5 3 2
3 4 1
выходные данные
18
ABBBBABBBB
входные данные
6
0A0BA0
5 3 2
3 4 1
выходные данные
17
AAABAB

Сдать задачу

Задать вопрос жюри по этой задаче