Background

About the past, Wen Zhaoxue has fragmented memories.

Problem Description

Specifically, she has $n$ memories. Each memory is a string of length at most $100$. The $i$-th memory $S_i$ lies at depth $r_i$ in her mind and has value $v_i$ to her.

Wen Zhaoxue is trying to recover the beauty in her memories, but there are simply too many and they are too complex. She can only think of a prefix segment $Q$ of her memories and the deepest position $d$ she can reach. Only memories that satisfy: the corresponding $Q$ is a prefix of $S_i$ and $r_i \le d$, can be recalled by Wen Zhaoxue.

Now, Wen Zhaoxue makes $m$ attempts. She wants to know, for each attempt, what the sum of values of all memories she can obtain is.

Input Format

The first line contains $n, m$.

The next $n$ lines each contain two integers $r_i, v_i$ and a string $S_i$, separated by spaces.

The next $m$ lines each contain an integer $d$ and a string $Q$, separated by spaces. It is guaranteed that $Q$ is a prefix of at least one $S_i$, but it is not guaranteed that there exists a memory that can actually be recalled.

Output Format

Output $m$ lines. Each line represents, for each attempt, the sum of values of all memories she can obtain.

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

Hint

Hint

In this problem, the definition of a prefix is as follows: for strings $S, P$, if $|P| \le |S|$ and for all $1 \le i \le |P|$ we have $S_i = P_i$, then $P$ is called a prefix of $S$.

Scale and Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1 \le |S_i|, |Q| \le 100$, $0 \le r_i, v_i, d \le 10^9$, and all strings consist only of lowercase letters.

Please pay attention to the impact of constant factors in time complexity.

Please consider using faster input/output methods.

Translated by ChatGPT 5