[R34B]括号回文串 - 代码源竞赛平台

时空限制

1S/512M

apiadu 喜欢回文串。

现在有一个长度为 $n$ 、仅由 ( 和 ) 组成的字符串 $s$ ，以及一个数组 $a$ （ $s$ 和 $a$ 的下标均从 $0$ 开始）。apiadu 可以对字符串 $s$ 进行任意次操作：

选择一个下标 $i$ ( $0 \leq i \leq n - 1$ )，花费 $a_i$ 个金币，将 $s$ 的第 $i$ 个字符进行翻转（即 ( 变为 )，) 变为 (）。

请帮 apiadu 计算将字符串 $s$ 变为一个回文串所需的最少金币数量。

一个字符串是回文串，当且仅当这个字符串从左向右读和从右向左读是完全一样的。例如，字符串 racecar 和 ()( 都是回文串，而 hello 和 (()) 则不是。

第一行包含一个正整数 $n$ ，表示字符串 $s$ 和代价数组 $a$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$ 。

第三行包含 $n$ 个正整数 $a_0, a_1, \ldots, a_{n-1}$ ，表示修改 $s$ 的第 $i$ 个位置需要的金币数量。

输出一个整数，表示将字符串 $s$ 变为回文串的最少金币数量。

8
())((())
1 2 3 4 5 6 7 8

修改位置为 $0,2$ 的字符，此时 $s$ 变成了 ))(((())。需要花费 $4$ 个金币。可以证明这是最少的花费金币数。

对于 $100\%$ 的数据， $1 \le n \le 10^5$ , $1 \le a_i \le 1000$ 。字符串 $s$ 仅由 ( 和 ) 组成。