#P18700. Strange Keyboard

    ID: 18036 传统题 1500ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-DijkstraTrie线性 DP消除被支配候选二叉堆

Strange Keyboard

Strange Keyboard

你有一块奇怪的键盘,上面有 NN 个普通按键和一个退格键。开始时,当前字符串为空。任何时候,你都可以按下这 N+1N+1 个按键中的任意一个。

按下第 ii 个普通按键,会把字符串 SiS_i 追加到当前字符串的末尾。

按下退格键时,如果当前字符串的长度小于 KK,则什么也不会发生;否则,删除当前字符串末尾的恰好 KK 个字符。

你想得到字符串 TT。判断是否能够做到;如果能够,求所需的最少按键次数。

输入格式

第一行包含整数 QQ,表示测试用例数。接下来依次给出各个测试用例。

每个测试用例的第一行包含两个整数 N,KN,K,分别表示普通按键数和每次有效退格删除的字符数。

接下来 NN 行,第 ii 行给出第 ii 个普通按键对应的字符串 SiS_i。

该测试用例的最后一行给出目标字符串 TT。

数据范围

  • 1≤Q≤1001\le Q\le100。
  • 1≤N≤1061\le N\le10^6。
  • 1≤K≤50001\le K\le5000。
  • 所有测试用例中,全部字符串 SiS_i 的长度总和不超过 10610^6。
  • 所有测试用例中,目标字符串 TT 的长度总和不超过 50005000。
  • 字符串 Si,TS_i,T 仅包含英文小写字母。

输出格式

对于每个测试用例输出一行:如果无法得到 TT,输出 -1;否则,输出得到 TT 所需的最少按键次数。

样例输入

2
2 3
defgh
abc
abcde
1 1
a
b

样例输出

3
-1

样例说明

在第一个测试用例中,可以进行如下操作:

  1. 按下第二个普通按键,得到 abc。
  2. 按下第一个普通按键,得到 abcdefgh。
  3. 按下退格键,得到所需的 abcde。

在第二个测试用例中,无法得到所需的字符串。