Во всех современных цифровых девайсах реализована экранная клавиатура, аналогичная клавиатуре для ПК — каждая буква на отдельной кнопке. Но так было не всегда — на первых телефонах долгое время клавиатура представляла из себя набор цифр 0–9 и некоторые дополнительные клавиши. Типовая схема клавиатуры представлена на рисунке.
Возьмём, к примеру, клавишу с цифрой 2. С помощью неё можно набрать буквы $$$a$$$, $$$b$$$, $$$c$$$. Чтобы набрать букву $$$a$$$, нужно один раз нажать на кнопку, чтобы набрать букву $$$b$$$ — два раза и т.д. Чтобы набрать подряд две буквы, которые находятся на одной кнопке (например, $$$ab$$$), придётся сначала набрать букву $$$a$$$, потом подождать $$$t$$$ секунд и набрать букву $$$b$$$ (иначе клавиатура не поймёт, что это две разные буквы). Но если пользователь ошибся, то он в любой момент может стереть одну или несколько подряд идущих последних букв нажатием специальной кнопки $$$\leftarrow$$$ (одно нажатие — одна удалённая буква). Однократное нажатие на любую кнопку занимает по времени $$$n$$$ секунд.
Пользователь хочет набрать на кнопочном телефоне сообщение $$$s$$$. Какое минимальное время он на это затратит?
В первой строке входных данных записана строка $$$s$$$ длиной не более $$$10^5$$$ символов, каждый из которых может быть произвольной строчной латинской буквой $$$(a - z)$$$.
Во второй строке записано целое число $$$t$$$ $$$(1 \leq t \leq 1000)$$$ — время ожидания в секундах.
В третьей строке записано целое число $$$n$$$ $$$(1 \leq n \leq 1000)$$$ — время нажатия на любую клавишу в секундах.
В качестве ответа выведите одно число — минимальное время в секундах, которое нужно затратить на написание сообщения.
mama102
8
kate410
60
В первом примере для набора буквы $$$m$$$ нужно один раз нажать на кнопку $$$6$$$, а для буквы $$$a$$$ — один раз на кнопку $$$2$$$. Каждое нажатие занимает $$$2$$$ секунды, значит это займет $$$8$$$ секунд.
Во втором примере для набора буквы $$$k$$$ нужно два раза нажать на кнопку $$$5$$$, для буквы $$$a$$$ — один раз на $$$1$$$, для буквы $$$t$$$ — один раз на $$$8$$$, а для $$$e$$$ — два раза на $$$3$$$. Итого, потребуется $$$6$$$ нажатий по $$$10$$$ секунд каждое, значит это займет $$$60$$$ секунд.
