You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

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$ 变为回文串的最少金币数量。

样例

样例输入 #1

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

样例输出 #1

4

样例解释 #1

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

数据规模

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