Gmo

Μια πολυεθνική εταιρεία σας ζητά να τη βοηθήσετε να τροποποιήσει γενετικά ένα μήλο. Προκειμένου τα μήλα να αναπτυχθούν πιο γρήγορα, να αποκτήσουν περισσότερα από αυτά, να γίνουν μεγαλύτερα και να φαίνονται πιο όμορφα και πιο συμμετρικά, το DNA του μήλου απαιτεί την εισαγωγή ενός συγκεκριμένου γονιδίου των χοίρων.

Το DNA του μήλου αντιπροσωπεύεται από μια σειρά χαρακτήρων από το σύνολο ~\{A,\;C,\;G,\;T\}~. Το απαιτούμενο γονίδιο των χοίρων αποτελείται επίσης από χαρακτήρες από αυτό το σύνολο. Το DNA του μήλου θα πρέπει να εγχυθεί με μερικούς χαρακτήρες σε ορισμένα σημεία, έτσι ώστε η προκύπτουσα αλληλουχία να περιέχει ένα γονίδιο χοίρου κάπου (σε διαδοχικές τοποθεσίες). Για να κάνουμε τα πράγματα λίγο πιο περίπλοκα, η εισαγωγή καθενός από τους χαρακτήρες ~A,\;C,\;G,\;T~ έχει το δικό του κόστος.

Βοηθήστε αυτήν την πολυεθνική εταιρεία να πετύχει τον στόχο της με το χαμηλότερο δυνατό συνολικό κόστος. Ως ανταμοιβή, παίρνετε έναν τόνο από τα μήλα τους.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει μια ακολουθία ~N\;(1 \leq N \leq 10\,000)~ χαρακτήρων που αντιπροσωπεύουν το DNA του μήλου.
Η δεύτερη γραμμή εισόδου περιέχει μια ακολουθία χαρακτήρων ~M\;(1 \leq M \leq 5\,000)~ που αντιπροσωπεύουν το γονίδιο των χοίρων που θέλουμε να εισαγάγουμε στο DNA του μήλου.
Και οι δύο ακολουθίες αποτελούνται μόνο από χαρακτήρες από το σύνολο ~\{A,\;C,\;G,\;T\}~.
Η τρίτη γραμμή εισόδου περιέχει τέσσερις ακέραιους αριθμούς από το διάστημα ~[0,\;1000]~: το κόστος εισαγωγής ενός χαρακτήρα ~A,\;C,\;G,\;T~, με αυτή τη σειρά.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει το ελάχιστο συνολικό κόστος.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~80~% των συνολικών πόντων, το ~N~ και το ~M~ δεν θα υπερβαίνουν τους ~2000~.

Παραδείγματα

input

GTA
CAT
5 7 1 3

output

10

Επεξήγηση του 1ου παραδείγματος:

Μερικές από τις πιθανές λύσεις είναι GCATA και GTCAT (οι χαρακτήρες που εισάγονται είναι έντονοι), η πρώτη λύση κοστίζει ~7 + 5~, η δεύτερη ~7 + 3~.

input

TATA
CACA
3 0 3 0

output

3

input

TCGCGAG
TGCAG
10 10 15 15

output

25