K - 括弧 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。

試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

( と ) からなる長さ N の文字列 S が与えられます。S の i 番目の文字を S_i で表します。

以下の手順で S を 括弧の対応が取れている文字列 (後述) にすることを考えます。

まず、次の操作を 0 回以上好きなだけ行います。

  • 1 \leq i \leq N を選ぶ。S_i が ( ならば ) に、) ならば ( に変更する。この操作のコストは C_i である。

その後、次の操作を行います。

  • S から 0 文字以上選んで削除し (全ての文字を削除しても良い)、削除しなかった文字を元の順序で繋げる。S の i 文字目を削除するコストは D_i である。

S を括弧の対応が取れている文字列にするための合計コストの最小値を求めてください。

なお、括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。

  • 空文字列
  • ある括弧の対応が取れている空でない文字列 A, B が存在し、 A , B をこの順に連結した文字列
  • ある括弧の対応が取れている文字列 A が存在し、 (, A, ) をこの順に連結した文字列

制約

  • 1 \leq N \leq 3000
  • S の長さは N
  • S の各文字は ( または )
  • 1 \leq C_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • N, C_i, D_i は整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

S を括弧の対応が取れている文字列にするための合計コストの最小値を出力せよ。

入力例 1

3
))(
3 5 7
2 6 5

出力例 1

8

はじめ S は ))( です。例えば次の手順で括弧の対応が取れている文字列にすることができます。

  • 文字を変更する段階で、S_1 を変更する。3 のコストがかかり、S は ()( となる。
  • 文字を削除する段階で、S_3 を削除する。5 のコストがかかり、S は () となる。

この場合の合計コストは 3+5=8 であり、これが最小です。

入力例 2

1
(
10
20

出力例 2

20

はじめ S は ( です。これを空文字列に変えるしかありません。

入力例 3

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

出力例 3

18

入力例 4

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

出力例 4

0

S は既に括弧の対応が取れている文字列です。

Score : 6 points

Warning

Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.

After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a string S of length N consisting of (s and )s. Let S_i denote the i-th character of S.

We want to make S a balanced string (defined below) in the following procedure.

First, we do the operation below zero or more times:

  • Choose an integer 1 \leq i \leq N. If S_i is (, replace it with ); if S_i is ), replace it with (. The cost of this operation is C_i.

Then, we do the operation below:

  • Choose zero or more (possibly all) characters in S and delete them. Then, concatenate the remaining characters in S without changing the order.

Find the minimum total cost required to make S a balanced string.

A balanced string is a string that is one of the following:

  • An empty string;
  • The concatenation of A and B in this order, for some non-empty balanced strings A and B;
  • The concatenation of (, A, and ) in this order, for some balanced string A/

Constraints

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum total cost required to make S a balanced string.

Sample Input 1

3
))(
3 5 7
2 6 5

Sample Output 1

8

S is initially ))(. One way to make it a balanced string is:

  • In the "modifying" step, change S_1 at the cost of 3. S becomes ()(.
  • In the "deleting" step, delete S_3 at the cost of 5. S becomes ().

The total cost here is 3+5=8, and this is the minimum possible value.

Sample Input 2

1
(
10
20

Sample Output 2

20

S is initially (, and the only choice is to make it an empty string.

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

S is already a balanced string.