[EPXLQ2024 fall round] 风吹起了从前

对于过去，温昭雪有着断断续续的记忆。

具体地，她有 $n$ 条记忆，每条记忆是一个长度不超过 $100$ 的字符串。第 $i$ 条记忆 $S_i$ 位于她心灵的 $r_i$ 深处，对她有 $v_i$ 的价值。 温昭雪正在试图恢复自己记忆中的美好，可记忆实在太多太复杂，她只能想到她记忆的一段前缀 $Q$ 和她能到达的最深位置 $d$。只有满足对应的 $Q$ 是 $S_i$ 的前缀且 $r_i \le d$ 的记忆才能被温昭雪回想到。 现在，温昭雪有 $m$ 次尝试。她想知道，对于每次尝试，她能获得的所有记忆价值之和是多少。

输入第一行包含 $n,m$。 以下 $n$ 行，每行两个整数 $r_i,v_i$ 和一个字符串 $S_i$，空格分隔。 以下 $m$ 行，每行一个整数 $d$ 和一个字符串 $Q$，空格分隔。保证 $Q$ 至少是某一个 $S_i$ 的前缀，**但不保证一定存在一个记忆能被回想到**。

输出 $m$ 行，每行表示对于每次尝试，她能获得的所有记忆价值之和是多少。

5 6
5 6 abcab
7 10 abcba
4 3 abc
3 6 ade
2 4 cde
2 abc
4 abc
5 abc
6 a
7 c
8 ab

0
3
9
15
4
19

### 提示 本题对前缀的定义为：对于字符串 $S,P$，若 $|P| \le |S|$ 且对所有 $1 \le i \le |P|$ 均有 $S_i=P_i$，则称 $P$ 是 $S$ 的前缀。 ### 数据规模与约定 **本题采用捆绑测试。** | $\text{Subtask}$ | $n \le$ | $ m\le$ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | :-: | | $0$ | $100$ | $100$ | | $11$ | | $1$ | $10^4$ | $10^5$ | $d = 10^9$ | $13$ | | $2$ | $10^4$ | $10^5$ | 字符串长度不超过 $2$ | $9$ | | $3$ | $10^4$ | $10^3$ | | $26$ | | $4$ | $10^4$ | $10^5$ | | $41$ | 对于所有数据，保证 $1 \le |S_i|,|Q| \le100, 0 \le r_i,v_i,d \le 10^9$，所有字符串仅由小写字母组成。 请注意时间复杂度常数因子带来的影响。 请考虑使用较快的输入输出方式。