A. Universal Paperclips
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Universal Paperclips — инкрементальная игра, целью которой является изготовление скрепок. В вашем распоряжении есть оборудование, производящее скрепки по нажатию кнопки.

В упрощенной версии игры для этой задачи будем считать, что игроку доступны два вида действий:

  1. Нажать на кнопку. Каждое нажатие добавляет определенное количество скрепок. Обозначается буквой «C» («click»).
  2. Улучшить процесс изготовления. Благодаря этому, каждое последующее нажатие на кнопку будет добавлять на одну скрепку больше. Обозначается буквой «U» («upgrade»).

Изначально у игрока ноль скрепок, а каждое нажатие на кнопку добавляет одну скрепку. На каждое улучшение тратится $$$x$$$ скрепок. Во всех входных данных гарантируется, что перед каждым улучшением в наличии есть хотя бы $$$x$$$ скрепок.

Бенни решил написать бота для этой игры. Он закодировал в бота последовательность из $$$n$$$ действий $$$S$$$, которую бот выполняет по циклу. Каждую секунду бот совершает очередное действие: на 1-й секунде бот применяет $$$S_1$$$, на второй — $$$S_2$$$, ..., на $$$n$$$-й — $$$S_n$$$, на $$$n+1$$$-й — снова $$$S_1$$$, и далее по циклу.

Сколько скрепок будет у Бенни после $$$t$$$ секунд работы его бота?

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

В первой строке содержатся три числа $$$n$$$, $$$t$$$ и $$$x$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le t \le 10^9$$$; $$$0 \le x \lt n$$$). Во второй строке содержится строка $$$S$$$ длины $$$n$$$ из символов «C» и «U».

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

Выведите одно число — число скрепок через $$$t$$$ секунд.

Система оценки
ПодзадачаБаллыОграничения
133$$$t \le 10^5$$$
267Без дополнительных ограничений
Примеры
Входные данные
10 15 2
CCCCCUUCCU
Выходные данные
25
Входные данные
3 10 0
UUU
Выходные данные
0
Входные данные
9 150 1
CCUCCCCUC
Выходные данные
2023
Примечание

Рассмотрим первый пример. Первые пять операций приносят по одной скрепке каждая. Следующие две операции используют по две скрепки, после чего остается одна скрепка, однако, следующие два нажатия производят по три скрепки. Далее, улучшение снова отбирает две. Последние пять нажатий приносят по 4 скрепки каждое.

Итоговое число скрепок равно $$$1 + 1 + 1 + 1 + 1 - 2 - 2 + 3 + 3 - 2 + 4 + 4 + 4 + 4 + 4 = 25$$$.