Network Billing Optimization

MY NS Middle School operates an educational network whose structure is a full binary tree. The tree has 2^N leaves, each representing a user with a unique ID from 1 to 2^N. The internal nodes represent routers and the edges represent cables. Initially each user chooses one of two payment methods: A or B. However, each user can change his/her payment method at a cost. Changing the payment method for user i costs C_i (the cost is incurred only if the user changes the originally registered payment method).

The network company bills the school using a peculiar "pairing billing" policy. For every pair of distinct users i and j (with 1 ≤ i < j ≤ 2^N), the following procedure is applied:

• In the network tree, find the lowest common ancestor (LCA) P of users i and j. (A node’s ancestors include its parent, its parent’s parent, and so on; the root has no ancestors.)
• Let the leaves governed by P be all the leaves in the subtree rooted at P (note that a leaf node does not govern any other leaf, only internal nodes govern leaves through their children).
• Denote by n_A and n_B the number of users in P's governed leaves who have chosen payment method A and B respectively.
• The billing rule at node P is given by the following formula: the pairing fee contributed by this pair equals F_P × (a_L · b_R + b_L · a_R) when combining the two subtrees of P (see below).

Remark: For any internal node P with left child covering a set of users with distribution (a_L users choosing A, b_L choosing B) and right child with distribution (a_R, b_R), the pairs of users for which P is the LCA cross between the two children. Thus the cost contributed at P is F_P × (a_L × b_R + b_L × a_R).

The total cost is the sum of:

1. The costs for switching payment methods (if a user changes method, the cost is C_i for user i).
2. The pairing fees computed at every internal node based on the distribution of chosen payment methods in its two children subtrees, using the above rule.

Your task is to help the school decide which payment method each user should choose (A or B) so that the overall cost (switching cost + billing fees) is minimized.

Input/Output Explanation: Under the hood the pairing fee is computed node‐by-node in the full binary tree formed by the network. The fee multiplier for each internal (router) node is given by F_P (in level order). For a leaf node (user), you are given the initial payment method and the cost to switch.

inputFormat

The input is given as follows:

N
S
C1 C2 ... C2N
F1 F2 ... F2N-1

• The first line contains an integer N (1 ≤ N ≤ 8) indicating the depth of the full binary tree (the number of user leaves is 2^N).
• The second line contains a string S of length 2^N consisting only of characters 'A' and 'B'. S[i] is the initially registered payment method for user i (users are numbered 1 to 2^N from left to right).
• The third line contains 2^N space‐separated integers, where the i-th integer is C_i, the cost for user i to change the payment method.
• The fourth line contains 2^N - 1 space‐separated integers. These represent the fee multipliers F for the internal nodes (routers) in level order (the root is first, then the left child and right child of the root, and so on).

You may assume that all costs and fee multipliers are nonnegative integers.

outputFormat

Output a single integer: the minimum total cost.

sample

2
ABBA
3 5 2 4
1 2 3

5

</p>