Bracket Sequence Transformation

You are given a valid parentheses sequence s of length \(2n\). Each left parenthesis in s is assigned a weight. You are also given two binary parameters \(x, y \in \{0,1\}\). You dislike the structure of two consecutive (adjacent) parentheses groups, i.e. a structure of the form \((A)(B)\) (where \(A\) and \(B\) are valid parentheses sequences), and you like the nested structure of the form \((A()B)\).

You can perform two types of operations to change the positions of brackets in s:

• Operation 1: If a substring of s has the form \[ p\,(A)(B)\,q, \] you may exchange the two brackets that separate \(A\) and \(B\) (turning the structure into a nested one of the form \((A()B)\)) with a cost given by \[ \text{cost} = x \times \bigl(\text{weight of the first left parenthesis in }(A)\bigr) + y \times \bigl(\text{weight of the first left parenthesis in }(B)\bigr). \] Note that the weights move together with their corresponding left brackets.
• Operation 2: If a substring of s has the form \[ p\,A\,B\,q, \] you may simply swap the entire segments \(A\) and \(B\) at no cost. (Here, p and q can be any strings, possibly empty; they are not necessarily valid sequences.)

Your goal is to transform \(s\) into a valid parentheses sequence which does not contain any occurrence of the disliked structure \((A)(B)\). In other words, the final sequence should be arranged so that no two top‐level valid parts appear consecutively; they must be merged into a nested structure instead. Using the two allowed operations (with swapping allowed arbitrarily for free), compute the minimum total cost needed to achieve such a transformation.

Note: Since Operation 2 allows free swaps, you may assume that you are free to reorder the \(n\) pairs arbitrarily. Therefore, the problem essentially reduces to merging the \(n\) pairs step by step into one completely nested structure. When merging two groups, say with first left-parenthesis weights \(a\) and \(b\), if you merge them (by the Operation 1), the cost incurred is:

[ \text{cost} = x \times a + y \times b. ]

Observe that after a merge, the leftmost left parenthesis (and its weight) of the merged structure is the same as that of the left group. With an appropriate reordering (using Operation 2), an optimal strategy is to always use the pair with the minimum weight as the leftmost element.

If you denote \(m = \min\{w_1, w_2, \dots, w_n\}\) (the minimal weight among the left parentheses) and \(S = \sum_{i=1}^{n} w_i\), then an optimal strategy yields:

• If \(x = 0\) and \(y = 0\): the total cost is \(0\).
• If exactly one of \(x, y\) is 1 (i.e. \(x+y=1\)): the total cost is \((n-1) \times m\).
• If \(x = 1\) and \(y = 1\): the total cost is \((n-1) \times m + (S - m)\). (Equivalently, \(S + (n-2) \times m\).)

Your task is to compute and output the minimum cost based on the input provided.

inputFormat

The input is given as follows:

1. The first line contains three integers \(n\), \(x\), and \(y\), where \(n\) is half the length of the valid parentheses sequence, and \(x, y \in \{0,1\}\).
2. The second line contains a string \(s\) of length \(2n\) consisting only of characters '(' and ')'. This string is a valid parentheses sequence.
3. The third line contains \(n\) space-separated integers, representing the weights of the left parentheses in the order they appear in \(s\).

outputFormat

Output a single integer, the minimum total cost required to transform \(s\) into a valid parentheses sequence that does not contain any occurrence of the disliked structure.

sample

3 1 1
()(() )
3 1 2

7