Description

Salieri discovered $n$ patterns for making music. He represents the $i$-th pattern as a string $s_i$, and the initial beauty of this pattern is $v_i$.
Now Salieri wants to produce $m$ pieces of music. Each time, his inspiration can be represented as a string $S$. Let $cnt_i$ be the number of occurrences of $s_i$ in $S$. Then the final beauty of the piece made using pattern $i$ is $w_i=cnt_i\times v_i$.
Of course, Salieri wants the final beauty to be as large as possible, but he found that under this inspiration, the top $k-1$ most beautiful pieces have already been made by Mozart, so he can only make the $k$-th most beautiful piece. Please output this final beauty.

Formal statement: Given $n$ strings $s_i$, each with a weight $v_i$. For each of the $m$ queries, you are given a string $S$ and a constant $k$. Let $cnt_i$ be the number of occurrences of $s_i$ in $S$. Find the $k$-th largest value among $cnt_i\times v_i$.

Input Format

The first line contains two integers $n,m$.
The next $n$ lines each contain a string $s_i$ and an integer $v_i$.
The next $m$ lines each contain a string $S$ and an integer $k$.

Output Format

Output one integer per line, representing the answer.

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

Hint

Let $L$ be the total length of all $s$.

For $100\%$ of the testdata, $1\le n,m\le10^5$, $L\le5\times10^5$.

At all times, $\sum |S|$ is of the same order as $L$. Only four characters $\texttt a,\texttt b,\texttt c,\texttt d$ will appear in $s$ and $S$. $v_i\le10^3$, and $k\le n$.

Translated by ChatGPT 5