29169번 - Производство паутины 다국어

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

Питер хочет найти наименее затратный процесс производства. Так как формула паутины секретна, для каждой паутины существует характеризующая ее строка, состоящая из строчных латинских букв. Таким образом, чтобы приготовить паутину, нужно собрать строку из пустой, с помощью следующих операций:

1. Добавить к текущей строке любую букву. Стоимость операции равна $a$.
2. Приписать к текущей строке ее же. Грубо говоря, продублировать строку. Стоимость операции равна $b$.
3. Удалить букву из конца текущей строки. Стоимость операции равна $c$.

Например из строки <<abc>>, можно получить строку <<abax>>, с помощью последовательности операций: $3,2,3,1$. Что будет суммарно стоить $a+b+2 c$.

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

К сожалению, в городе была замечена Зловещая Шестерка, и Человеку-пауку нужно с этим разобраться. Раз уж Вы знаете его альтер эго, можно доверить Вам написание программы, которая сможет вычислить наименьшую стоимость производства паутины по ее характеризующей строке.

В первой строке входного файла содержится одно целое число $n$ ($1 \le n \le 100\,000$) --- длина строки, характеризующей паутину. Во второй строке входного файла дана строка длиной $n$, состоящая из строчных латинских букв. В третьей строке входного файла заданы три целых числа $a, b, с$ ($0 \le a, b, c \le 10^9$) --- стоимость добавления одной буквы, дублирования строки и удаления одной буквы из конца соответственно.

В единственной строке выходного файла выведите одно целое число --- наименьшую суммарную стоимость операций, с помощью которых можно получить данную строку.

В первом тесте нужно купить все буквы.

Во втором тесте нужно купить буквы <<a>>, <<b>>, <<c>>, <<d>>, потом продублировать строку и удалить <<d>>.