Due to the (lack of) quality in the previous test cases that Jeffrey generated, his test cases are now frowned upon to use by the other problem setters. In an effort to restore his destroyed reputation in the Case Creation Community (CCC), Jeffrey is going through all of the input files he has, word by word, to improve the quality of his test data!
Jeffrey knows that if he doesn't have good quality test cases this week, he will forever be shamed in the CCC and could never make it to the prestigious Case Creation Organization (CCO). However, it is also a commonly known fact in the CCC that Jeffrey is a slow and lazy typer! For a given word in the input file, ~A~, Jeffrey would like to transform it to a new word, ~B~. In Jeffrey's world (filled with angry typing, mechanical keyboards, VIM and Linux), he has three different operations to transform the word.
- Delete a character from ~A~ using ~D~ seconds.
- Insert a character into ~A~ using ~I~ seconds.
- Replace a character in ~A~ with a new character using ~R~ seconds.
The difference in time for the different operations is obviously due to his loud mechanical keyboard.
Before Jeffrey starts going through all the words, he would like to know how long it will take for him to go through each word so he can find the total time to allocate out of his day. Of course, Jeffrey only wants to know the minimum amount of time he needs to fix each word, he needs all of the remaining time in his day to post dank memes online as a publicity stunt for maximum likes and comments. With this, he could gain enough popularity to be nominated to join the Case Creation Organization!
On the first line will be three space separated integers:
- ~D~ ~(0 \leq D \leq 1\,000)~: The amount of time in seconds required to delete a character
- ~I~ ~(0 \leq I \leq 1\,000)~: The amount of time in seconds required to insert a character
- ~R~ ~(0 \leq R \leq 1\,000)~: The amount of time in seconds required to replace a character
The next line will contain two space separated strings, ~A~ and ~B~. It is guaranteed that the length of ~A~ and ~B~ will be less than or equal to ~1000~.
Output the cheapest cost to transform word ~A~ to word ~B~.
1 2 4 intention execution