Problem Description

You are given a string $ S $ of length $ N $ consisting of ( and ). Let $ S_i $ denote the $ i $-th character of $ S $.

Consider transforming $ S $ into a properly balanced bracket string (defined below).

First, perform the following operation any number of times (including zero):

• Choose an index $1 \leq i \leq N$. If $ S_i $ is (, change it to ); if $ S_i $ is ), change it to (. The cost of this operation is $ C_i $.

Then, perform the following operation:

• Remove any number of characters from $ S $ (including all characters), and concatenate the remaining characters in their original order. The cost of removing the $ i $-th character of $ S $ is $ D_i $.

Find the minimum total cost to transform $ S $ into a properly balanced bracket string.

A properly balanced bracket string is defined as a string that satisfies one of the following conditions:

• An empty string
• There exist non-empty properly balanced bracket strings $ A $ and $ B $ such that the string is the concatenation of $ A $ and $ B $ in this order
• There exists a properly balanced bracket string $ A $ such that the string is the concatenation of (, $ A $, and ) in this order

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $ $ C_1 $ $ C_2 $ $\cdots$ $ C_N $ $ D_1 $ $ D_2 $ $\cdots$ $ D_N $

Output Format

Output the minimum total cost to transform $ S $ into a properly balanced bracket string.

Sample Input and Output

Sample Input #1

3
))(
3 5 7
2 6 5

Sample Output #1

8

Sample Input #2

1
(
10
20

Sample Output #2

20

Sample Input #3

10
))())((()(
13 18 17 3 20 20 6 14 14 2
20 1 19 5 2 19 2 19 9 4

Sample Output #3

18

Sample Input #4

4
()()
17 8 3 19
5 3 16 3

Sample Output #4

0

Notes/Hints

Constraints

• $1 \leq N \leq 3000$
• The length of $ S $ is $ N $
• Each character of $ S $ is either ( or )
• $1 \leq C_i \leq 10^9$
• $1 \leq D_i \leq 10^9$
• $ N $, $ C_i $, and $ D_i $ are integers

Sample Explanation 1

Initially, $ S $ is ))(. For example, it can be transformed into a properly balanced bracket string as follows:
- In the character change phase, change $ S_1 $. This costs $ 3 $, and $ S $ becomes ()(
- In the character removal phase, remove $ S_3 $. This costs $ 5 $, and $ S $ becomes ()
The total cost in this case is $ 3 + 5 = 8 $, which is the minimum.

Sample Explanation 2

Initially, $ S $ is (. The only way to transform it is to make it an empty string.

Sample Explanation 4

$ S $ is already a properly balanced bracket string.

见题面 Input 部分

见题面 Output 部分