Một công ty đa quốc gia đang nhờ bạn giúp họ biến đổi gen một quả táo. Để những quả táo phát triển nhanh hơn, thu được nhiều quả hơn, to hơn và trông đẹp hơn và giống hơn, DNA của quả táo cần được đưa vào một gen nhất định của lợn.

DNA của quả táo được biểu thị bằng một chuỗi ký tự từ tập hợp {A, C, G, T}. Gen lợn cần thiết cũng bao gồm các ký tự từ bộ này. DNA của quả táo nên được tiêm một số ký tự vào một số vị trí để chuỗi kết quả chứa gen lợn ở đâu đó (ở các vị trí kế tiếp nhau). Để làm cho mọi thứ phức tạp hơn một chút, việc chèn từng ký tự A, C, G, T đều có chi phí riêng.

Giúp công ty đa quốc gia này đạt được mục tiêu của họ với tổng chi phí thấp nhất có thể. Như một phần thưởng, bạn sẽ nhận được rất nhiều táo của họ.

Input

• Dòng đầu tiên chứa một chuỗi ~N~ ~(1 ≤ N ≤ 10 000)~ ký tự đại diện cho DNA của quả táo.
• Dòng đầu vào thứ hai chứa một chuỗi gồm ~M~ ~(1 ≤ M ≤ 5 000)~ ký tự đại diện cho gen lợn mà chúng ta muốn chèn vào DNA của quả táo.
• Cả hai chuỗi chỉ bao gồm các ký tự từ tập hợp {A, C, G, T}.
• Dòng thứ ba chứa bốn số nguyên trong khoảng ~[0, 1000]~: giá trị của việc chèn một ký tự A, C, G, T theo thứ tự đó.

Output

• Dòng đầu tiên và duy nhất phải chứa tổng chi phí tối thiểu.

Scoring

• Trong các bài kiểm tra chiếm 80% tổng số điểm, ~N~ và ~M~ sẽ không vượt quá ~2000~.

Sample Input 1

GTA
CAT
5 7 1 3

Sample Output 1

10

Sample Input 2

TATA
CACA
3 0 3 0

Sample Output 2

3

Sample Input 3

TCGCGAG
TGCAG
10 10 15 15

Sample Output 3

25

Làm rõ ví dụ đầu tiên: Một số giải pháp khả thi là GCATA và GTCAT (các ký tự được chèn được in đậm), giải pháp đầu tiên có giá 7 + 5, giải pháp thứ hai là 7 + 3.