문제
당신에게는 X, Y의 두 문자열이 있다.
처음에 두 문자열은 모두 비어있다.
당신은 3가지 연산을 쓸 수 있다.
연산 1 : A의 비용을 들여 X 뒤에 알파벳 소문자 하나를 추가한다.
연산 2 : B의 비용을 들여 Y를 X로 만들고 X는 빈 문자열로 만든다.
연산 3 : C의 비용을 들여 X 뒤에 Y의 내용을 붙여 넣는다.
당신은 주어진 문자열 S를 X에 입력하고 싶다.
필요한 최소의 비용은 얼마일까?
입력
다음과 같은 형식으로 입력이 주어진다.
N
S
A
B
C
<입력 제한>
- 1 <= N <= 2500
- S는 길이 N의 문자열
- S는 알파벳 소문자로 이루어져 있다.
- 1 <= A <= 1 000 000 000
- 1 <= B <= 1 000 000 000
- 1 <= C <= 1 000 000 000
<서브태스크>
#1 (1점) : N = 3
#2 (5점) : S의 모든 글자가 'a'로 이루어져 있다.
#3 (14점) : N <= 30
#4 (10점) : N <= 200
#5 (32점) : N <= 1000
#6 (38점) : 추가적인 제한 조건이 없다.
출력
S의 문자열을 X에 입력하는데 드는 최소 비용을 출력하라.
예제1
입력
11
mississippi
10
5
2
출력
88
출처
JOI spring camp 2022