[JRKSJ R4] Salieri

 ~~【记得到番里面去把“萨列里谱不出莫扎特的曲子”这句话找到】~~ 最终还是没能找到，哪位看过《命运石之门0》的兄弟能帮我找找？

Salieri 发现了 $n$ 种制作音乐的模式，他将第 $i$ 种模式表示为一个字符串 $s_i$，这种模式所带来的初始优美度为 $v_i$。 Salieri 现在想制作 $m$ 首乐曲，每次他的灵感可以被表示成一个字符串 $S$。设 $cnt_i$ 为 $s_i$ 在 $S$ 中的出现次数，则采用 $i$ 模式制作的乐曲最终的优美度 $w_i=cnt_i\times v_i$。 Salieri 当然希望制作出来的乐曲最终优美度越大越好，但是他发现此灵感下前 $k-1$ 优美的乐曲已经被 Mozart 制作过了，他只能制作第 $k$ 优美的乐曲。请你求出这个最终优美度。 形式化题意：给出 $n$ 个字符串 $s_i$，每个字符串有一个权值 $v_i$。$m$ 次询问每次给出一个字符串 $S$ 和一个常数 $k$。设 $cnt_i$ 为 $s_i$ 在 $S$ 中的出现次数，求 $cnt_i\times v_i$ 第 $k$ 大的值。

第一行两个数，$n,m$。 接下来 $n$ 行每行一个字符串 $s_i$ 和一个数 $v_i$。 接下来 $m$ 行每行一个字符串 $S$ 和一个数 $k$。

每行一个数，代表答案。

4 2
ab 2
a 2
ba 2
b 1
bbaba 2
aab 1

4
4

15 4
ba 18
cbc 74
aac 54
ba 77
a 66
c 96
cdb 47
dc 45
cb 62
db 88
dda 93
db 34
b 81
acd 100
da 80
bcaacbbdcbabcda 4
bccac 3
abdbaca 5
cbdaaaacaaca 3

124
66
77
108

设 $L$ 为 $s$ 长度总和。 | $\text{Subtask}$|$n,m\le$|$L\le$|特殊性质| 分值 | |:-:|:-:|:-:|:-:| :-: | |$1$|$10^3$|$5\times10^3$|无| $10$ | |$2$|$10^3$|$10^5$|无| $20$ | |$3$|$10^5$|$5\times10^5$|$k=1$| $10$ | |$4$|$3\times10^4$|$2\times10^5$|$k\le5$| $20$ | |$5$|$3\times10^4$|$2\times10^5$|无| $20$ | |$6$|$10^5$|$5\times10^5$|无| $20$ | 对于 $100\%$ 的数据，$1\le n,m\le10^5$，$L\le5\times10^5$。 无论何时 $\sum |S|$ 与 $L$ 同阶，$s$ 和 $S$ 中只会出现 $\texttt a,\texttt b,\texttt c,\texttt d$ 四种字符，$v_i\le10^3$，$k\le n$。