問題文

( と ) のみからなる文字列を括弧列と呼ぶことにします。

長さ $2N$ の括弧列 $S$ があります。

$i$ 文字目は $A_i$ のコストを払うことで、 (を )に、 )を (に入れ替えることができます。

括弧列 $S$ を整合している状態にするためのコストの最小値を答えてください。

括弧列 $S$ に対して、連続する $2$ 文字が () である箇所を除去する操作を $0$ 回以上繰り返すことで空文字にできるとき、括弧列 $S$ は整合しているといいます。

入力

$N$
$S$
$A_1$ $A_2$ $\ldots$ $A_{2N}$

制約

• $1 \le N \le 1000$
• $|S|=2N$
• $S$ は(と)のみからなる
• $1 \le A_i \le 10^{9}$
• $N,A_i$ は整数

出力

括弧列 $S$ を整合している状態にするためのコストの最小値を出力してください。

最後に改行してください。

サンプル

3
)(((()
10 22 3 5 2 13

15

4
()(()())
3141592 653589 793238 462643 38327 9502884 1971 69399375

0

5
((((((((((
1 2 3 4 5 6 7 8 9 10

30