F. Foreign Language
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pedro Vieira finally got accepted to his internship at AMAN (commonly referred to as the Academy of Many Amazing Netizens), and unfortunately for him, they speak a really strange language there. However, he only discovered this fact after etching a commemorative phrase onto a plaque, and now he wants to modify it into the strange language spoken at AMAN.

Vieira thinks that it'll be too much of a hassle to make a new plaque from scratch, so he asks for help from a friend who's able to perform certain modifications to the plaque. This friend is able to (don't ask how, though) insert letters anywhere in the phrase, remove them or simply modify them, each having their own respective cost.

Knowing that spaces are a non-issue, given the original phrase and the one in the strange language, Pedro Vieira wants to find out what's the minimum cost in order for this change to be done.

Input

The first line of the input contains 5 integers $$$n, m, a, b, c$$$ $$$(1 \leq n, m \leq 2 \times 10^3)$$$, $$$(1 \leq a, b, c \leq 10^9)$$$ — the length of the phrase on the plaque, the length of the phrase in the strange language, the cost of inserting letters, the cost of removing them and the cost of modifying them, respectively.

The next line contains string $$$s$$$ $$$(|s| = n)$$$ — the phrase on the plaque.

The next line contains string $$$t$$$ $$$(|t| = m)$$$ — the phrase in the strange language.

Both strings contain letters of the English alphabet and note that capital and lowercase letters are considered different.

Output

Output a single integer — the minimum cost of correcting the plaque.

Examples
Input
9 11 827 3281 921
ILoveAMAN
beepbopobep
Output
9943
Input
3 4 19 28 3
Abc
abcd
Output
22