C. Сжать строку
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имеется строка $$$s$$$ из $$$n$$$ символов. Каждый символ — маленькая латинская буква. Вам нужно сжать эту строку, потратив как можно меньше денег.

Для сжатия вы должны представить строку $$$s$$$ в виде конкатенации некоторого количества непустых строк: $$$s = t_{1} t_{2} \ldots t_{k}$$$. Далее, $$$i$$$-ю из этих строк нужно сжать одним из следующих двух способов:

  • если $$$|t_{i}| = 1$$$, то есть текущая строка состоит всего из одного символа, то можно просто заплатить $$$a$$$ монет;
  • если $$$t_{i}$$$ является подстрокой строки $$$t_{1} t_{2} \ldots t_{i - 1}$$$, то можно заплатить $$$b$$$ монет.

Строка $$$x$$$ является подстрокой строки $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

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

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

В первой строке находятся три целых положительных числа, разделённых пробелами: $$$n$$$, $$$a$$$ и $$$b$$$ ($$$1 \leq n, a, b \leq 5000$$$) — длина строки, стоимость сжатия строки из одного символа и стоимость сжатия подстроки, которая встречалась ранее, соответственно.

Во второй строке находится строка $$$s$$$, состоящая из $$$n$$$ строчных латинских букв.

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

Выведите единственное число — наименьшее возможное количество монет, небходимое для сжатия.

Примеры
Входные данные
3 3 1
aba
Выходные данные
7
Входные данные
4 1 1
abcd
Выходные данные
4
Входные данные
4 10 1
aaaa
Выходные данные
12
Примечание

В первом тесте можно положить $$$t_{1} =$$$ «a», $$$t_{2} =$$$ «b», $$$t_{3} =$$$ «a» и заплатить $$$3 + 3 + 1 = 7$$$ монет, поскольку $$$t_{3}$$$ является подстрокой строки $$$t_{1}t_{2}$$$.

Во втором тестовом примере нужно сжать каждую букву независимо.

В третьем тесте можно положить $$$t_{1} = t_{2} =$$$ «a», $$$t_{3} =$$$ «aa» и заплатить $$$10 + 1 + 1 = 12$$$ монет, поскольку $$$t_{2}$$$ – подстрока $$$t_{1}$$$, а $$$t_{3}$$$ – подстрока $$$t_{1} t_{2}$$$.