Gomamayo 序列

题目描述

给定一个由 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;反之,则将其变为 0。若执行该操作,所需花费为 $C_i$。

求使 $S$ 成为好字符串所需的最小总花费。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $S$ 是由 0 和 1 组成、长度为 $N$ 的字符串。
• $1 \leq C_i \leq 10^9$
• $N$ 和 $C_i$ 是整数。