#P18700. Strange Keyboard
Strange Keyboard
Strange Keyboard
你有一块奇怪的键盘,上面有 个普通按键和一个退格键。开始时,当前字符串为空。任何时候,你都可以按下这 个按键中的任意一个。
按下第 个普通按键,会把字符串 追加到当前字符串的末尾。
按下退格键时,如果当前字符串的长度小于 ,则什么也不会发生;否则,删除当前字符串末尾的恰好 个字符。
你想得到字符串 。判断是否能够做到;如果能够,求所需的最少按键次数。
输入格式
第一行包含整数 ,表示测试用例数。接下来依次给出各个测试用例。
每个测试用例的第一行包含两个整数 ,分别表示普通按键数和每次有效退格删除的字符数。
接下来 行,第 行给出第 个普通按键对应的字符串 。
该测试用例的最后一行给出目标字符串 。
数据范围
- 。
- 。
- 。
- 所有测试用例中,全部字符串 的长度总和不超过 。
- 所有测试用例中,目标字符串 的长度总和不超过 。
- 字符串 仅包含英文小写字母。
输出格式
对于每个测试用例输出一行:如果无法得到 ,输出 -1;否则,输出得到 所需的最少按键次数。
样例输入
2
2 3
defgh
abc
abcde
1 1
a
b
样例输出
3
-1
样例说明
在第一个测试用例中,可以进行如下操作:
- 按下第二个普通按键,得到
abc。 - 按下第一个普通按键,得到
abcdefgh。 - 按下退格键,得到所需的
abcde。
在第二个测试用例中,无法得到所需的字符串。