该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个字符串, 长度为 $n$, 并且仅包含包含字符 $0, 1$, 以及一个长度为 $n$ 的正整数数组$c_1,c_2,...c_n$, 其中 $c_i$ 表示在位置 $i$ 发起一次后缀翻转操作的代价,其中,在位置 $i$ 发起的一次后缀翻转操作指

对$s_i$及$s_i$后面的每个字符进行反置操作, 即将0变成1, 1变成0;

请计算使得字符串单调不降所需的最小总代价。

Format

Input

第一行输入一个整数$n (1 \leq n \leq 2 * 10^5)$, 表示数组长度。

第二行输入一个长度为$n$, 由字符0, 1构成的字符串。

第三行输入$n$个整数$c_1,c_2,...,c_n(1 \leq c_i \leq 10^9)$, 代表第i个整数$c_i$表示在位置i发起一次后缀翻转操作的代价。

Output

输出单调不降最小总代价。

Samples

3
010
2 1 3

1

Limitation

1s, 1024KiB for each test case.