题目背景

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

题目描述

具体地，她有 $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$ 的前缀。

数据规模与约定

本题采用捆绑测试。

对于所有数据，保证 $1 \le |S_i|,|Q| \le100, 0 \le r_i,v_i,d \le 10^9$，所有字符串仅由小写字母组成。

请注意时间复杂度常数因子带来的影响。

请考虑使用较快的输入输出方式。