Задача 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 (ноль), означающих, какой вид газона можно использовать для данного участка.
В третьей строке содержатся целые числа p1, d1, s1 (1 ≤ s1 < p1 ≤ 105, 2 ≤ d1 ≤ 105), описанные в условии задачи.
В четвёртой строке содержатся целые числа p2, d2, s2 (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