← 返回题目列表

AtCoder · abc346_d

G. Gomamayo 序列

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个字符串 S 长度 N 组成 0 和 1.

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

  • 正好有一个整数 i 这样 1 \leq i \leq N - 1 和 i-th 和 自记录开始以来,第 (i + 1)第一个字符 T 是相同的。

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

  • 如果 i- 第一个字符 S is 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,并且不可能使 S 一个好的字符串小于 7,所以打印 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