유전자 변형 사과

어느 다국적 기업이 사과의 유전자를 조작하는 일을 도와달라고 한다. 사과가 더 빨리 자라고, 더 많이 달리고, 더 크고, 보기 좋고 좌우가 고르게 되려면 사과의 DNA에 특정한 돼지 유전자를 끼워 넣어야 한다.

사과의 DNA는 A, C, G, T 네 문자로 이루어진 문자열로 나타낸다. 끼워 넣어야 하는 돼지 유전자도 같은 네 문자로 이루어져 있다. 사과의 DNA에서 원하는 위치마다 문자를 삽입해서, 완성된 문자열 안에 돼지 유전자가 연속한 구간으로 나타나게 만들어야 한다. 여기서 조금 더 까다로운 점은 A, C, G, T를 하나 삽입하는 비용이 문자마다 다르다는 것이다.

삽입 비용의 총합이 가장 적어지도록 이 기업의 목표를 이루어 주자. 보상으로 사과 1톤을 받는다.

첫째 줄에 사과의 DNA를 나타내는 길이 $N$의 문자열이 주어진다. ($1 \le N \le 10000$)

둘째 줄에 끼워 넣으려는 돼지 유전자를 나타내는 길이 $M$의 문자열이 주어진다. ($1 \le M \le 5000$)

두 문자열은 모두 A, C, G, T로만 이루어져 있다.

셋째 줄에 정수 네 개가 주어진다. 차례대로 A, C, G, T를 하나 삽입하는 비용이고, 네 값은 모두 0 이상 1000 이하이다.

첫째 줄에 삽입 비용의 총합이 될 수 있는 가장 작은 값을 출력한다.

첫 번째 예제를 살펴보자. 돼지 유전자가 연속으로 나타나게 만드는 방법은 여러 가지이다. 예를 들어 GCATA는 비용이 7 + 5이고, GTCAT는 7 + 3이다. 굵게 쓴 문자가 새로 삽입한 문자이다.