问题描述

给定一个由 0 和 1 组成的长度为 $N$ 的字符串 $S$。

由 0 和 1 组成的长度为 $N$ 的字符串 $T$ 是一个好字符串，当且仅当它满足以下条件:

• 恰好存在一个整数 $i$，使得 $1\leq i\leq N-1$，并且 $T$ 的第 $i$ 个和第 $(i+1)$ 个字符相同。

对于每个 $i=1,2,\ldots,N$，您可以选择是否执行一次以下操作：

如果 $S$ 的第 $i$ 个字符为 0，则将其替换为 1，反之亦然。此操作的成本（如果执行）是 $C_i$。

找出使 $S$ 成为一个好字符串所需的最小总成本。

数据规模

$2\leq N\leq 2×10^5$

$S$ 是由 0 和 1 组成的长度为 $N$ 的字符串。

$1\leq C_i\leq 10^9$

$N$ 和 $C_i$ 是整数。

输入

输入来自标准输入，格式如下:

$N$

$S$

$C_1\ C_2\ \ldots\ C_N$

输出

打印答案。

5
00011
3 9 2 6 4

7

对 $i=1,5$ 执行该操作，而对 $i=2,3,4$ 不执行该操作，则 $S=10010$，这是一个好的字符串。这种情况下产生的成本是 7，小于 7 是不可能让 $S$ 成为一个好的字符串的，所以打印 7。

4
1001
1 2 3 4

0

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

2286846953