103463: [Atcoder]ABC346 D - Gomamayo Sequence

Problem Statement

You are given a string $S$ of length $N$ consisting of 0 and 1.

A string $T$ of length $N$ consisting of 0 and 1 is a good string if and only if it satisfies the following condition:

• There is exactly one integer $i$ such that $1 \leq i \leq N - 1$ and the $i$-th and $(i + 1)$-th characters of $T$ are the same.

For each $i = 1,2,\ldots, N$, you can choose whether or not to perform the following operation once:

• If the $i$-th character of $S$ is 0, replace it with 1, and vice versa. The cost of this operation, if performed, is $C_i$.

Find the minimum total cost required to make $S$ a good string.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $S$ is a string of length $N$ consisting of 0 and 1.
• $1 \leq C_i \leq 10^9$
• $N$ and $C_i$ are integers.

Input

The input is given from Standard Input in the following format:

$N$
$S$
$C_1$ $C_2$ $\ldots$ $C_N$

Output

Print the answer.

Sample Input 1

5
00011
3 9 2 6 4

Sample Output 1

7

Performing the operation for $i = 1, 5$ and not performing it for $i = 2, 3, 4$ makes $S =$ 10010, which is a good string. The cost incurred in this case is $7$, and it is impossible to make $S$ a good string for less than $7$, so print $7$.

Sample Input 2

4
1001
1 2 3 4

Sample Output 2

0

Sample Input 3

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

Sample Output 3

2286846953

问题描述

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

长度为N的字符串T由字符0和1组成，只有当满足以下条件时，它才是一个好字符串：

• 存在一个整数$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 \times 10^5$
• S是一个长度为N的字符串，由字符0和1组成。
• $1 \leq C_i \leq 10^9$
• N和$C_i$都是整数。

输入

输入从标准输入以以下格式给出：

$N$
$S$
$C_1$ $C_2$ $\ldots$ $C_N$

输出

输出答案。

样例输入1

5
00011
3 9 2 6 4

样例输出1

7

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

样例输入2

4
1001
1 2 3 4

样例输出2

0

样例输入3

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

样例输出3

2286846953