|
||||||||||
Display SubstringTime Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1428 Accepted Submission(s): 431 Problem Description When we display a string on a LED screen, there may be different energy consumptions for displaying different characters. Given a string $S$ with length $n$ consisting of lowercase English letters and the energy consumption of each letter. Assume that the energy consumption of a string is the sum of the energy consumptions of all its characters. Please find the $k$-th smallest energy consumption of all the $\textbf{different}$ substrings of $S$. Note that a substring of a string $S$ is a contiguous subsequence of $S$. We say two strings $S$ and $T$ are different if the lengths of them are different or there exists at least one position $i$ satisfying $S[i] \neq T[i]$. Input The first line of the input contains an integer $T \ (1 \leq T \leq 2 \times 10^3)$ --- the number of test cases. The first line of each test case contains two integers $n \ (1 \leq n \leq 10^5)$ and $k \ (1 \leq k \leq \frac{n (n + 1)}{2})$. The second line of each test case contains a string $S$ with length $n$ consisting of lowercase English letters. The third line of each test case contains $26$ integers $c_a, c_b, \ldots, c_z \ (1 \leq c_{\alpha} \leq 100)$ --- the energy consumption of each letter. It is guaranteed that the sum of $n$ among all test cases does not exceed $8 \times 10^5$. Output For each test case, output a single integer in a separate line --- the $k$-th smallest energy consumption, or $-1$ if there is no answer. Sample Input
Sample Output
Source | ||||||||||
|