5373: Display Substring
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
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 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]≠T[i].
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]≠T[i].
输入
The first line of the input contains an integer T (1≤T≤2×103) --- the number of test cases.
The first line of each test case contains two integers n (1≤n≤105) and k (1≤k≤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 ca,cb,…,cz (1≤cα≤100) --- the energy consumption of each letter.
It is guaranteed that the sum of n among all test cases does not exceed 8×105.
The first line of each test case contains two integers n (1≤n≤105) and k (1≤k≤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 ca,cb,…,cz (1≤cα≤100) --- the energy consumption of each letter.
It is guaranteed that the sum of n among all test cases does not exceed 8×105.
输出
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