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.

2
5 5
ababc
3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 15
ababc
3 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

4
-1