403049: GYM100981 G Камень-ножницы-бумага

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Камень-ножницы-бумагаограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Петя и Вася играют в известную игру «Камень-ножницы-бумага». Игра проходит в n раундов. В каждом раунде Петя и Вася выбирают одну из трёх фигур: камень, ножницы или бумагу. Если фигуры игроков не совпали, победитель определяется стандартным способом (камень побеждает ножницы, ножницы побеждают бумагу, бумага побеждает камень), иначе объявляется ничья. За победу присуждается w очков, за ничью — d очков, за поражение — 0 очков. Итоговый счёт каждого игрока — это сумма очков по всем раундам.

Петя заранее определил, какую фигуру он будет выбирать в каждом раунде, и записал это в виде строки длины n из букв «r», «s» и «p». Здесь буква «r» на i-й позиции в строке означает, что в i-м раунде Петя выберет камень, «s» — ножницы, а «p» — бумагу.

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

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

Первая строка входных данных содержит три целых числа n, w и d (1 ≤ n ≤ 100 000, 0 ≤ d ≤ w ≤ 109) — количество раундов, количество очков за победу и количество очков за ничью соответственно.

Вторая строка содержит строку длины n, состоящую из символов «r», «s», «p», — циклический сдвиг записанной Петей строки.

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

Выведите одно число — максимальный счёт, который может гарантировать себе Вася.

ПримерыВходные данные
3 3 1
rsp
Выходные данные
6
Входные данные
5 1 0
sssss
Выходные данные
5
Входные данные
3 5 2
psp
Выходные данные
12
Примечание

В первом примере после первого раунда Вася может точно определить строку Пети и выиграть оставшиеся раунды, набрав 6 очков.

Во втором примере Вася может всегда выбирать камень и обеспечить себе победу во всех пяти раундах, набрав таким образом 5 очков.

В третьем примере, выбирая постоянно ножницы, Вася выиграет два раунда, а в оставшемся раунде будет объявлена ничья. Таким образом, Вася может гарантировать себе 2·5 + 1·2 = 12 очков.

加入题单

上一题 下一题 算法标签: