I. Bracket
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Starlight Glimmer has a bracket sequence $$$s$$$ of lenght $$$n$$$, which only contains character '(', ')' and '?'.

She also has a value sequence $$$v$$$ of lenght $$$n$$$ constructed by two integer constants $$$a,b$$$ that $$$v_i=ai+b$$$.

Define that the partition of a sequence is a pair sequence $$$(l_i,r_i)$$$ of length $$$m$$$ if it satisfies $$$l_1\le r_1 \lt l_2\le r_2 \lt \dots \lt l_{m-1}\le r_{m-1} \lt l_m\le r_m$$$ and any substring $$$(l_i,r_i)$$$ is a valid bracket sequence.

The substring $$$(l,r)$$$ of $$$s$$$ is a string removed first $$$l-1$$$ characters and last $$$n-r$$$ characters of $$$s$$$, and Starlight Glimmer believes it valid if:

  • Each character of it is either '(' or ')';
  • The number of '(' is no less than the number of ')' for any prefix;
  • The number of '(' is equal to the number of ')' for it.

According to the above, Starlight Glimmer defines the value of $$$s$$$ is $$$\max_{partition}\sum v_{r_i+1-l_i}$$$.

Now Starlight Glimmer should and find the maximal value of $$$s$$$ if she replace all '?' to '(' or ')' in a optimal way.

Input

The first line contains a single integer $$$n\ (1\le n\le 5\times 10^5)$$$ - the length of $$$s$$$.

The second line contains a string $$$s$$$ of lenght $$$n$$$ - denoting the bracket sequence $$$s$$$.

The third line contains two integer $$$a,b\ (-10^6\le a,b\le 10^6)$$$ - denoting $$$v_i=ai+b$$$.

Output

Print a single integer - the maximal value of $$$s$$$ after replacement.

Example
Input
10
(?)(??(?)?
1 2
Output
14
Note

For the testcase, $$$v=[3,4,5,6,7,8,9,10,11,12]$$$.

The result of a possible replacement is '(()()(()))', and Starlight Glimmer could choose $$$(2,3),(4,5),(6,9)$$$ as a partition, the value of it is $$$v_2+v_2+v_4=4+4+6=14$$$.