P8147 [JRKSJ R4] Salieri

 ~~[Remember to find the line “Salieri can’t compose Mozart’s music” in the anime.]~~ In the end I still couldn’t find it. Can anyone who has watched *Steins;Gate 0* help me find it?

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$.

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 one integer per line, representing the answer.

Let $L$ be the total length of all $s$. | $\text{Subtask}$|$n,m\le$|$L\le$|Special property| Score | |:-:|:-:|:-:|:-:| :-: | |$1$|$10^3$|$5\times10^3$|None| $10$ | |$2$|$10^3$|$10^5$|None| $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$|None| $20$ | |$6$|$10^5$|$5\times10^5$|None| $20$ | 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