(본 문제에서 언급된 미슈트 염기 서열은 지어낸 말이므로 실제로는 없을 수 있음)

사과는 달콤하기 때문에 벌레가 꼬기 쉬운 과일이다. 생명공학자인 신우는 사과의 DNA에 염기를 집어넣어서 벌레가 꼬이지 않게 하려고 한다. 신우는 사과의 염기 서열과 미슈트 염기 서열을 알고 있는데, 사과의 DNA가 미슈트 염기 서열을 포함하고(연속해야 함) 있으면 벌레가 꼬이지 않는다고 한다. 허나, 4개의 염기들이 화학구조가 모두 다르기 때문에 A(아데닌), C(시토신), G(구아닌), T(티민) 염기를 삽입하는 데 드는 비용이 각기 다르다. 신우는 총 비용을 최소화해서 벌레가 꼬이지 않는 사과를 만들려고 한다. 신우를 도와 총 비용으로 가능한 최솟값을 구하는 프로그램을 작성하여라.

입력 형식

• 첫 번째 줄에는 사과의 염기 서열 (10,000글자 이내)이 주어진다.
• 두 번째 줄에는 미슈트 염기 서열 (5,000글자 이내)이 주어진다.
• 세 번째 줄에는 A, C, G, T를 삽입하는 데 드는 비용을 나타내는 0 이상 1,000 이하의 정수가 주어진다.

출력 형식

입력 예 1

GTA
CAT
5 7 1 3

출력 예 1

10

입력 예 2

TATA
CACA
3 0 3 0

출력 예 2

3


입력 예 3

TCGCGAG
TGCAG
10 10 15 15

출력 예 3

25


입력 예 1 설명
가능한 경우는 GCATA와 GTCAT가 있는데, 각각 7+5, 7+3의 비용이 든다.

The apple's DNA is represented by a series of characters from the set {A, C, G, T}. The required swine gene is also comprised of charaters from this set. The apple's DNA should be injected with some characters into some places, so that the resulting sequence contains a swine gene somewhere (in successive locations). To make things a bit more complicated, inserting each of the characters A, C, G, T has its own cost.

Help this multinational company in achieving their goal with the lowest possible total cost. As a reward, you get a ton of their apples.

INPUT

• The first line of input contains a sequence of N (1 ≤ N ≤ 10 000) characters which represent the apple's DNA.
• The second line of input contains a sequence of M (1 ≤ M ≤ 5 000) characters which represent the swine gene that we want to insert into the apple's DNA.
  Both the sequences are comprised only of characters from the set {A, C, G, T}.
• The third line of input contains four integers from the interval [0, 1000]: the cost of inserting one character A, C, G, T, in that order.

OUTPUT

SCORING

SAMPLE TESTS

input

GTA
CAT
5 7 1 3

output

10

input

TATA
CACA
3 0 3 0

output

3

input

TCGCGAG
TGCAG
10 10 15 15

output

25

출처:coci/2013-2014/contest4 2번
번역:functionx