\(4^{th}\) round, January \(18^{th}\), 2014

A multinational company is asking you to help them genetically modify an apple. In order for the
apples to grow faster, to get more of them, to make them bigger and make them look nicer and more
simmetrical, the apple's DNA requires an insertion of a certain swine gene.

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.

In test cases worth 80% of total points, N and M will not exceed 2000.

\(4^{th}\) round, January \(18^{th}\), 2014

The first line of input contains a sequence of N (\(1 \le N \le 10\,000\)) characters which represent the
apple's DNA.
The second line of input contains a sequence of M (\(1 \le M \le 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.

The first and only line of output must contains the minimal total cost.

생성자가 기록되지 않았습니다.

출처 COCI 2013/2014 Contest 4