AT_past202004_k 括弧

给定一个长度为 $n$ ，且仅由`(`和`)`组成的字符串 $s$（下标从 $1$ 开始）。现在，我们希望花费最少的代价，使得 $s$ 成为一个“平衡字符串”（定义后面会给出）。 首先，我们决定从 $s$ 中挑出 $0$ 个或更多字符，并将其改变（即括号方向改成相反的）。第 $i$ 个字符执行此操作的代价为 $c_i$。 然后，我们决定从 $s$ 中挑出 $0$ 个或更多（全部挑出也可）个字符并将其删除。第 $i$ 个字符执行此操作的代价为 $d_i$。删除完毕后，按顺序连接 $s$ 中的字符。 请求出让 $s$ 成为“平衡字符串”的最小代价。 **“平衡字符串”的定义：** 一个“平衡字符串”可以是： - 一个空串； - 由两个非空平衡字符串 $a$ 和 $b$ 连接而成的串； - 在平衡字符串 $a$ 的两侧分别加上`(`和`)`后连成的字符串。

第一行：$n$。 第二行：$s$。 第三行：$c_1,c_2,...,c_n$。 第四行：$d_1,d_2,...,d_n$。

一行一个整数，最小代价。 ### 限制条件 - $1 \le n \le 3000$； - $s$ 的长度为 $n$，且仅由`(`和`)`组成； - $1 \le c_i,d_i \le 10^9$； - $n,c_i,d_i$ 均为整数。

### 注意 この問題に対する言及は、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 $ は既に括弧の対応が取れている文字列です。