You are given a string and your task is to make the string increasing. A string is called increasing if the following is true:

      ∀, : <

i.e., the ASCII value of every character of the given string is less than or equal to any of its preceding characters.

Given the cost of changing every character to every other character, what is the minimum cost to make a given string increasing?

Input Format

The first line contains an integer, , the number of test cases. test cases follow, each containing lines:
The first line of each test case, contains the string .
Each of the next lines contain space-separated integers. The first line is cost of changing one to any other letter, the second line is the cost of changing one to any other letter, and so on.
Diagonal of this x table will be zero (there is no cost if you don't change a letter).

Constraints

length of string
cost of changing letters
Input string contains only lower case letters 'a' to 'z'.

Output Format

For each test case, print in a new line the minimum cost and the increasing string you made using minimum cost, separated with a space.
If there are several such strings, print the lexicographically smallest string.

Sample Input

1
mehdi
0 87 55 45 15 50 35 34 40 96 90 57 77 92 80 18 56 53 19 78 11 13 74 65 8 16
89 0 48 39 59 74 7 21 6 66 18 75 19 13 95 38 32 67 75 92 38 72 58 59 86 94
88 76 0 8 30 91 79 67 91 23 25 72 37 12 98 30 2 47 12 69 21 36 12 98 84 42
59 3 80 0 87 80 7 98 54 19 4 49 45 41 11 5 76 67 32 25 3 40 47 84 24 19
90 52 73 68 0 31 25 99 10 84 37 43 81 62 64 31 69 3 94 68 2 55 42 98 57 32
21 85 91 17 60 0 32 1 56 38 71 12 39 61 16 25 33 15 1 55 57 20 31 72 55 66
43 66 38 39 74 63 0 84 18 9 63 67 1 15 44 64 18 65 50 62 93 96 32 54 57 49
95 41 13 67 26 33 76 0 98 73 39 88 47 9 16 47 68 96 66 0 81 54 94 73 11 20
12 40 60 44 39 51 88 60 0 97 51 42 5 93 41 9 91 71 72 93 96 47 49 33 66 14
44 99 13 82 22 2 56 73 15 0 66 19 95 91 29 5 83 31 56 7 82 85 93 92 50 0
48 74 83 4 24 46 51 10 99 59 0 15 62 81 64 96 22 29 2 23 10 28 20 17 9 2
70 30 39 81 77 32 35 9 45 10 99 0 1 6 17 29 8 75 35 93 32 43 34 20 61 18
71 83 53 96 28 28 71 88 55 76 14 44 0 36 34 67 59 41 30 5 19 91 94 43 24 68
58 19 61 15 26 35 73 43 23 85 17 12 93 0 11 68 94 75 78 62 60 76 42 46 4 99
55 22 87 85 86 92 63 73 19 82 99 83 18 57 0 63 57 11 71 69 63 2 66 71 57 71
96 30 66 83 88 82 47 79 49 91 73 12 6 52 31 0 52 38 81 87 38 9 38 11 4 42
34 55 17 18 30 49 69 8 79 96 65 15 81 93 86 38 0 88 22 62 46 22 28 48 93 99
32 19 48 66 57 75 82 81 76 59 48 66 20 58 32 43 17 0 28 70 19 94 63 19 38 18
31 8 15 35 17 75 55 28 14 12 61 73 16 7 16 59 89 88 0 65 78 72 59 61 5 68
17 41 81 38 94 32 38 47 68 89 65 14 48 90 11 35 20 60 76 0 31 33 20 60 66 94
61 6 55 52 75 94 14 63 75 60 56 93 68 17 98 54 57 73 71 36 0 80 78 56 72 19
61 33 40 9 58 42 30 11 92 25 37 63 5 89 2 68 43 36 14 80 13 0 69 6 19 16
33 36 73 81 15 52 77 25 17 76 30 58 29 48 58 70 52 41 74 21 42 41 0 26 83 10
88 5 74 71 17 58 98 55 2 16 95 75 92 64 43 20 54 77 51 40 13 96 9 0 79 20
92 44 84 4 99 76 55 7 47 73 77 57 52 58 37 27 98 52 29 40 62 61 88 16 0 36
26 42 71 43 56 31 66 36 2 23 64 32 53 57 67 17 10 85 51 55 80 24 68 7 78 0

Sample Output

20 mrtuz

Explanation

m changes to m with cost 0
e changes to r with cost 3
h changes to t with cost 0
d changes to u with cost 3
i changes to z with cost 14
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score