PIET's EC department students are working on a set of conductors to create a circuit with maximum resistance.

The simplest circuit consists of a single conductor (i.e., a single piece of wire). Each such circuit is labeled using the string "X".

Students are using two different ways to connect two simpler circuits into one new, more complex circuit. Note that these are not the standard two ways (connecting in series and in parallel), so read the following description carefully.

If student uses the type-A connection, the resistance of the new circuit is the sum of the resistances of the two original circuits. If student uses the type-B connection, the resistance of the new circuit is the maximum of the resistances of the two original circuits. Suppose that the two original circuits had labels C1 and C2. Then we use the label "A"+C1+C2 for a new circuit constructed from them using the type-A connection, and the label "B"+C1+C2 if type-B connection was used. For example, "AXX" is the label of the circuit obtained by using a type-A connection on two conductors.

You are given a String circuit with a valid label of a circuit. You are also given a list conductors with as many elements as the number of occurrences of 'X' in circuit. The elements of conductors are the resistances of all conductors you are going to use to construct the circuit described by circuit. Each of the conductors can only be used once. Each of the conductors can be used as each of the 'X's. Calculate the largest possible resistance of the constructed circuit.

Input :

First Line of input contains an integer T, denoting number of test cases.

Each test case contains two lines of input where first line contains an input string S having the labels of the conductors and type of circuits.

Second line contains a list of integers denoting the resistance of each conductor and number of integers is equal to the number of 'X' label in the string in same order.

Output :

Print the maximum resistance for each test case.

Constraints :

• Each character in circuit will be 'A', 'B', or 'X'.
• Circuit will be a valid circuit label according to the problem statement.
• conductors will contain between 1 and 2,000 elements, inclusive.
• Each element of conductors will be between 1 and 100,000, inclusive.
• The number of occurrences of the character 'X' in circuit will be equal to the number of elements of conductors.