Description

给定$n$个长度不超过 10 的字符串以及$m$次询问，每次询问给出一个字符串和一个操作次数上限。
对于每次询问，请你求出给定的n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

Input Format

第一行包含两个整数n和m。
接下来n行，每行包含一个字符串，表示给定的字符串。
再接下来m行，每行包含一个字符串和一个整数，表示一次询问。
字符串中只包含小写字母，且长度均不超过 10。

Output Format

输出共m行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

3 2
abc
acd
bcd
ab 1
acbd 2

1
3

Hint

1≤$n,m$≤1000,

Source

2.5动态规划 线性DP