题目描述

小 Z 手上有个长度为 $n$ 的只包含 0,1的字符串 $S$，目标是让字符串变成单调不降（即所有 $0$ 都在 $1$ 之前，也可全为 $0$ 或 $1$）。

字符串的每个位置都可以进行任意次后缀翻转的操作，如选择位置 $i$，则将 $i\sim n$ 的每一个位置都进行零一翻转互换，每次需花费相应的代价 $a_i$。

询问完成要求的最小代价。

输入格式

第一行，$1$ 个正整数 $n$。

第二行，长度为 $n$ 的字符串 $S$。

第三行，$n$ 个正整数 $a_i$，表示每个位置 $i$ 进行后缀翻转的代价。

输出格式

$1$ 个整数，表示最后成为单调不降字符串的最小花费。

输入输出样例

3
010
2 1 3

1

样例 $\tt \#1$说明

• 在位置 $2$ 进行一次后缀翻转成为 001 即可，花费为 $1$

3
001
2 1 3

0

数据范围

• 对于 $60\%$ 的数据，$n\le 10^3$
• 对于 $100\%$ 的数据，$1\le n\le 2\times10^5,1\le a_i\le 10^9,S_i∈{0,1}$