Music Mode Beauty

Salieri discovered \(n\) music production modes. The \(i\)-th mode is represented by a string \(s_i\) and has an initial beauty value \(v_i\). For each of the \(m\) queries, an inspirational string \(S\) is given. For each mode, let \(cnt_i\) be the number of times string \(s_i\) occurs in \(S\) (using non-overlapping matching). The final beauty for mode \(i\) is computed as \(w_i = cnt_i \times v_i\).

However, the top \(k-1\) most beautiful pieces (those with the highest \(w_i\)) have already been produced, and Salieri must produce the \(k\)-th most beautiful piece. Your task is to determine the \(k\)-th largest value among all \(w_i\). Note that if multiple modes share the same beauty value, they are all considered separately in the ranking.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) separated by a space, representing the number of music modes and the number of queries, respectively.

The next \(n\) lines each contain a string \(s_i\) and an integer \(v_i\) separated by a space, representing the mode and its initial beauty value.

Then, for each query, there are two lines: the first line is the inspirational string \(S\) and the second line is an integer \(k\), indicating that you must output the \(k\)-th largest \(w_i\) among all modes.

outputFormat

For each query, output a single line containing the \(k\)-th largest beauty value \(w_i\).

sample

3 2
abc 2
a 1
b 3
ababc
2
aaa
1

2
3