P11412 [EPXLQ2024 fall round] The Wind Stirred Up the Past

About the past, Wen Zhaoxue has fragmented memories.

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.

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 $m$ lines. Each line represents, for each attempt, the sum of values of all memories she can obtain.

### 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.** | $\text{Subtask}$ | $n \le$ | $ m \le$ | Special property | Score | | :-: | :-: | :-: | :-: | :-: | | $0$ | $100$ | $100$ | | $11$ | | $1$ | $10^4$ | $10^5$ | $d = 10^9$ | $13$ | | $2$ | $10^4$ | $10^5$ | String length is at most $2$ | $9$ | | $3$ | $10^4$ | $10^3$ | | $26$ | | $4$ | $10^4$ | $10^5$ | | $41$ | 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