Nutter is a weird kid. As an infant, he was obsessed with the prefixes of "nutt" ("nut", "nu", and "n"), but hated the word "nutt" itself. When his parents bought him a box of Scrabble, he realized that the board already contained a single word: "putt", which got him thinking. He wondered how he could add, swap, or remove blocks from a word ~A~ to make all the prefixes of another word ~B~.
Nutter has access to an infinite supply of Scrabble blocks, and can only add, swap, or remove blocks to form his desired prefixes. Each operation takes 1 move, but since he's quick with his hands, he isn't worrying about shifting blocks (you can add, swap, or remove non-terminal blocks). Nutter wants to know how he can turn word ~A~ into word ~B~'s prefixes (not including word ~B~ itself) using the minimum number of moves.
Subtask 1 [20%]: ~\,1 \le N, M \le 10~.
Subtask 2 [80%]: ~\,1 \le N, M \le 10\,000~.
The first line of input will contain two integers ~N~ and ~M~ separated by a single space. The second line will contain a single string ~A~ of length ~N~, and the third line will contain a single string ~B~ of length ~M~.
Output a single integer representing the minimum number of moves to change word ~A~ to all of word ~B~'s prefixes.
4 4 nutt putt
The prefixes of "putt" are "put", "pu", and "p", and Nutter wants to try and make them all from the word "nutt".
To get "put" from "nutt", swap the "n" with a "p" and remove a "t" from the end (2 operations).
To get "pu", do the same operations as "put", but remove another "t" (3 operations + 2 = 5 total).
To get "p", do the same operations as "pu", but remove the "u" at the end (4 operations + 5 = 9 total).
Since Nutter doesn't want to make "putt" itself, he uses 9 operations in total.