Text Editor
Contest: Educational Codeforces Round 131 (Rated for Div. 2)
Difficulty rating: 2500
Tags: brute force, dp, greedy, strings

You wanted to write a text $$$t$$$ consisting of $$$m$$$ lowercase Latin letters. But instead, you have written a text $$$s$$$ consisting of $$$n$$$ lowercase Latin letters, and now you want to fix it by obtaining the text $$$t$$$ from the text $$$s$$$.

Initially, the cursor of your text editor is at the end of the text $$$s$$$ (after its last character). In one move, you can do one of the following actions:

- press the "left" button, so the cursor is moved to the left by one position (or does nothing if it is pointing at the beginning of the text, i. e. before its first character);
- press the "right" button, so the cursor is moved to the right by one position (or does nothing if it is pointing at the end of the text, i. e. after its last character);
- press the "home" button, so the cursor is moved to the beginning of the text (before the first character of the text);
- press the "end" button, so the cursor is moved to the end of the text (after the last character of the text);
- press the "backspace" button, so the character before the cursor is removed from the text (if there is no such character, nothing happens).

Your task is to calculate the minimum number of moves required to obtain the text $$$t$$$ from the text $$$s$$$ using the given set of actions, or determine it is impossible to obtain the text $$$t$$$ from the text $$$s$$$.

You have to answer $$$T$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$T$$$ ($$$1 \le T \le 5000$$$) — the number of test cases. Then $$$T$$$ test cases follow.

The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 5000$$$) — the length of $$$s$$$ and the length of $$$t$$$, respectively.

The second line of the test case contains the string $$$s$$$ consisting of $$$n$$$ lowercase Latin letters.

The third line of the test case contains the string $$$t$$$ consisting of $$$m$$$ lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$ ($$$\sum n \le 5000$$$).

Output format:
For each test case, print one integer — the minimum number of moves required to obtain the text $$$t$$$ from the text $$$s$$$ using the given set of actions, or -1 if it is impossible to obtain the text $$$t$$$ from the text $$$s$$$ in the given test case.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6
9 4
aaaaaaaaa
aaaa
7 3
abacaba
aaa
5 4
aabcd
abcd
4 2
abba
bb
6 4
baraka
baka
8 7
question
problem

Example output:
5
6
3
4
4
-1

Editorial:
Of course, there is no need to press "home" more than once (and no need to press "end" at all), because suppose we did something on suffix, then pressed "home", did something on prefix and then pressed "end" and continue doing something on suffix. Then we can merge these two sequences of moves on suffix and press "home" after we did anything we wanted on suffix, and the answer will not get worse.
Now, let's iterate over the position $$$pos$$$ at which we will press "home" (in range from $$$0$$$ to $$$n$$$). In other words, we iterate over the position till which we press only "left" and "backspace" to fix the suffix. So now we have the string $$$s[pos; n)$$$ and we want to get some suffix of $$$t$$$ from this string, but we actually don't know which suffix of $$$t$$$ we want. So let's iterate over the length of this suffix $$$suf$$$ in a range from $$$0$$$ to $$$m$$$. Now we have the string $$$s[pos; n)$$$ and the string $$$t[m - suf; m)$$$ and we have to check if we can obtain this suffix of $$$t$$$ from this suffix of $$$s$$$. This part can be precalculated in $$$O(n)$$$ greedily (we just can store for each suffix of $$$t$$$ the rightmost position in $$$s$$$ in which this suffix is obtainable). If we can obtain the current suffix, then we obviously can say the number of moves to do that — it is $$$n - pos$$$ and actually do not depend on the suffix length (because if we meet the character we need, we just press "left" and move to the next character, otherwise we press "backspace" and move to the next character deleting the one we don't need).
After that, we press "home" and now we have to check if we can obtain $$$t[0; m - suf)$$$ from $$$s[0; pos)$$$. This part can also be precalculated greedily in $$$O(n)$$$ like the part with rightmost positions for suffixes. But the minimum number of moves required to obtain the prefix is tricky. Actually, if we consider these prefixes from right to left, we want to match as many characters from the beginning as possible. In other words, if we reverse $$$s[0; pos)$$$ and $$$t[0; m - suf)$$$, we want to find their longest common prefix, and this will be the number of characters we don't want to touch at all (and if it is the longest common prefix, it means that the next character is bad, and we want to remove it anyway, so the length of LCP of these two reversed prefixes is the only thing affecting the number of moves on the prefix). This part can be precalculated in $$$O(n^2)$$$ with simple dynamic programming (using $$$O(n^2)$$$ memory) or with z-function in $$$O(n^2)$$$ time and $$$O(n)$$$ memory — we just need to build a z-function on a string $$$s[0; pos)^{-1} + \# + t^{-1}$$$, where $$$+$$$ is the concatenation of strings and $$$-1$$$ is the reverse operation. The required value of the z-function for the fixed values $$$pos$$$ and $$$suf$$$ will be in the position $$$pos + 1 + m - suf$$$. And the answer for the prefix will be $$$pos - suf$$$ (this is the number of extra characters on the prefix we have to delete) plus $$$pos - z_{pos + 1 + m - suf}$$$ plus $$$1$$$ because we have to press "home". But there is a corner case. If the prefix is empty, then we don't need to do all of this and the answer for prefix will be $$$0$$$.
Complexity: $$$O(n^2)$$$ time and $$$O(n)$$$ memory.