当我们加入一个串后，我们一定是保留它的一个前缀，添加一些新的串使得除掉该前缀后总长度是 $K$ 的倍数，再将这部分全部删除。设最终添加的总长度是 $L$，串个数是 $C$，代价就是 $(L-|T|)/K+C$。整体乘上 $K$，我们可以认为一个串的代价就是 $|S|+K$。

对每个串，我们把它添加到 Trie 上，并且枚举它的每个前缀，计算保留该前缀的代价。设剩余部分的长度是 $l$，我们需要找到一些串长度总和加上 $l$ 是 $K$ 的倍数，且代价和最小。显然这是一个同余最短路的问题。我们对每种不同的长度跑一次同余最短路，每次是 $O(K)$ 的（只需要在 $i\to i+|S|$ 形成的环上从前向后更新两遍）。设 $L=\sum |S_i|$，则只有 $O(\sqrt L)$ 种不同的长度，总复杂度 $O(K\sqrt L)$。

最后进行 DP，设 $dp(i)$ 表示已经匹配了 $T$ 的前 $i$ 个字符的最小代价，转移直接枚举这次加的串 $T[i,j)$，转移到 $dp(j)$，代价直接在 Trie 上查询。

总时间复杂度 $O(L+K\sqrt L+|T|^2)$。

多组数据会影响 $O(K\sqrt L)$ 这部分的复杂度，变成 $O(K\sqrt {QL})$。