Sort The Strings

Ninja has an array, ‘S’, of ‘N’ words, each word consisting of lowercase English letters. An array of words is good if they are in lexicographical order. Ninja would like to make the array ‘S’ good. However, the only move Ninja can perform is to reverse any number of them as many times as he wants.

Let ‘A[i]’ be the cost to reverse the word ‘S[i]’. Let ‘C’ be the minimum total cost to make the array ‘S’ good. Calculate the value of ‘C’. If it’s impossible to make the array good, return the integer ‘-1’.

Example :

N = 3, A = [ 4, 8, 6 ], S = [ “tb”, “ay”, “yb” ]
For each string, we have 2 choices, whether to reverse it or not.
For [ “tb”, “ay”, “yb”], not sorted in lexicographical order.
For [ “tb”, “ay”, “by”], not sorted in lexicographical order.
For [ “tb”, “ya”, “yb”], sorted in lexicographical order and the cost is 0 + 8 + 0 = 8.
For [ “tb”, “ya”, “by”], not sorted in lexicographical order.
For [ “bt”, “ay”, “yb”], not sorted in lexicographical order.
For [ “bt”, “ay”, “by”], not sorted in lexicographical order.
For [ “bt”, “ya”, “yb”], sorted in lexicographical order and the cost is 4 + 8 + 0 = 12.
For [ “bt”, “ya”, “by”], not sorted in lexicographical order.
Hence, the answer is 8.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains a single integer, ‘N’, denoting the number of strings.

The second line contains ‘N’ space-separated integers denoting the elements of the cost array ‘A’.

The next ‘N’ lines contain the array ‘S’ elements, a single string containing lowercase English letters per line.

Output Format :

For each test case, calculate the minimum total cost to make the array ‘S’ good. Return the integer ‘-1’ if it’s impossible.

Output for each test case will be printed on a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
0 ≤ A[i] ≤ 10^4
1 ≤ ∑ len(S[i]) ≤ 10^6

Time limit: 1 sec