{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ of length $2N$ consisting of the characters `(` and `)`. Let $S_i$ denote the $i$\\-th character from the left of $S$.\nYou can perform the following two types of operations zero or more times in any order:\n\n*   Choose a pair of integers $(i,j)$ such that $1\\leq i < j \\leq 2N$. Swap $S_i$ and $S_j$. The cost of this operation is $A$.\n    \n*   Choose an integer $i$ such that $1\\leq i \\leq 2N$. Replace $S_i$ with `(` or `)`. The cost of this operation is $B$.\n    \n\nYour goal is to make $S$ a correct parenthesis sequence. Find the minimum total cost required to achieve this goal. It can be proved that the goal can always be achieved with a finite number of operations.\nWhat is a correct parenthesis sequence? A correct parenthesis sequence is a string that satisfies any of the following conditions:\n\n*   It is an empty string.\n*   It is formed by concatenating `(`, $A$, `)` in this order where $A$ is a correct parenthesis sequence.\n*   It is formed by concatenating $A$ and $B$ in this order where $A$ and $B$ are correct parenthesis sequences."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\leq N \\leq 5\\times 10^5$\n*   $1\\leq A,B\\leq 10^9$\n*   $S$ is a string of length $2N$ consisting of the characters `(` and `)`."},{"iden":"input","content":"The Input is given from Standard Input in the following format:\n\n$N$ $A$ $B$\n$S$"},{"iden":"sample input 1","content":"3 3 2\n)))(()"},{"iden":"sample output 1","content":"5\n\nHere is one way to operate:\n\n*   Swap $S_3$ and $S_4$. $S$ becomes `))()()`. The cost is $3$.\n*   Replace $S_1$ with `(`. $S$ becomes `()()()`, which is a correct parentheses sequence. The cost is $2$.\n\nIn this case, we have made $S$ a correct bracket sequence for a total cost of $5$. There is no way to make $S$ a correct bracket sequence for less than $5$."},{"iden":"sample input 2","content":"1 175 1000000000\n()"},{"iden":"sample output 2","content":"0\n\nThe given $S$ is already a correct bracket sequence, so no operation is needed."},{"iden":"sample input 3","content":"7 2622 26092458\n))()((((()()(("},{"iden":"sample output 3","content":"52187538"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}