You have to make a word dictionary for NLP study. A string is given to you of length n that consists of lowercase alphabets. An array of size 26 is also given to show the numeric value for each alphabet. You should display the subsequence of a particular size whose sum of values is maximum. If multiple subsequences are available, then print the subsequence which would come earlier in any normal dictionary. Input format The first line contains an integer t representing the number of test cases. For each test case, you are given two integers n and k, a string s, and an array A of length 26. n=number of characters in string, k=the size of the desired subsequence Output format Print a string for each test case. Example Input 2 6 3 cadbca 5 2 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 5 abcabc 100 50 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Output aca abcac
You have to make a word dictionary for NLP study. A string is given to you of length n that consists of lowercase alphabets. An array of size 26 is also given to show the numeric value for each alphabet. You should display the subsequence of a particular size whose sum of values is maximum. If multiple subsequences are available, then print the subsequence which would come earlier in any normal dictionary.
Input format
The first line contains an integer t representing the number of test cases.
For each test case, you are given two integers n and k, a string s, and an array A of length 26. n=number of characters in string, k=the size of the desired subsequence
Output format
Print a string for each test case.
Example
Input
2
6 3
cadbca
5 2 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 5
abcabc
100 50 80 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
aca
abcac
Step by step
Solved in 3 steps with 1 images