题目描述

给你一个长度为 $n$ 的 $01$ 字符串 $S$ ，定义一个好字符串为：有且仅有一个 $1 \le i \lt n$ ，满足 $s_i = s_{i+1}$ 。

把字符串的第 $i$ 位翻转的代价是 $c_i$ ，问把字符串 $S$ 改为好字符串需要的最小代价是多少。

输入格式

第一行输入一个整数 $n$ 。

第二行输入字符串 $S$ 。

第三行输入 $n$ 个整数 $c_1,c_2,...,c_n$ 。

输出格式

输出题目要求的答案。

输入输出样例 #1

输入 #1

5
00011
3 9 2 6 4

输出 #1

7

可以选择翻转第一位和第五位，代价是 $7$ ，这是最小代价。

输入输出样例 #2

输入 #2

4
1001
1 2 3 4

输出 #2

0

输入输出样例 #3

输入 #3

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

输出 #3

2286846953

说明/提示

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $S$ 只包含 $0$ 和 $1$ 。
• $1\ \leq\ C_i\ \leq\ 10^9$