AT_past202004_k 括弧

[problemUrl]: https://atcoder.jp/contests/past202004-open/tasks/past202004_k `(` と `)` からなる長さ $ 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 $, `)` をこの順に連結した文字列

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $ $ C_1 $ $ C_2 $ $ \cdots $ $ C_N $ $ D_1 $ $ D_2 $ $ \cdots $ $ D_N $

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

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ は整数 ### Sample Explanation 1 はじめ $ S $ は `))(` です。例えば次の手順で括弧の対応が取れている文字列にすることができます。 - 文字を変更する段階で、$ S_1 $ を変更する。$ 3 $ のコストがかかり、$ S $ は `()(` となる。 - 文字を削除する段階で、$ S_3 $ を削除する。$ 5 $ のコストがかかり、$ S $ は `()` となる。 この場合の合計コストは $ 3+5=8 $ であり、これが最小です。 ### Sample Explanation 2 はじめ $ S $ は `(` です。これを空文字列に変えるしかありません。 ### Sample Explanation 4 $ S $ は既に括弧の対応が取れている文字列です。