2150. ДНК

Транснациональная компания просит вас помочь им генетически модифицировать арбуз. Для того, чтобы семечки из арбуза сами разбегались, в ДНК арбузов требуется вставку определенного гена таракана.

ДНК арбуза представлена последовательностью символов из набора {A, C, G, T}. Требуемый ген таракана также состоит из символов этого множества. В ДНК арбуза нужно вставить некоторые символы, так чтобы в полученной последовательности получился ген таракана (как некоторая непрерывная подпоследовательность). Чтобы усложнить вашу задачу, вставка каждого из символов A, C, G, T имеет свою стоимость. Помогите транснациональной компании в достижении этой цели с минимально возможной общей стоимостью. В качестве награды вы получите тонну таких арбузов.

Первая строка ввода содержит последовательность из `N` (`1\ ≤\ N\ ≤\ 10\ 000`) символов, которые представляют ДНК арбуза.

Вторая строка содержит последовательность из `M` (`1\ ≤\ M\ ≤\ 5\ 000`) символов, которые представляют ген таракана, который нужно вставить в ДНК арбуза.

Обе последовательности состоят только из символов из множества {A, C, G, T}.

Третья строка ввода содержит четыре целых числа из интервала [0, 1000] – cтоимость вставки одного символа A, C, G, T, именно в таком порядке.

Первая и единственная строка вывода должен содержит минимальную общую стоимость.

GTA
CAT
5 7 1 3

10

TATA
CACA
3 0 3 0

3

TCGCGAG
TGCAG
10 10 15 15

25

Пояснение к первому примеру: Возможными вариантами решения являются GCATA и GTCAT (вставленные символы выделены жирным шрифтом), первый вариант имеет стоимость `7\ +\ 5`, второй – `7\ +\ 3`.