小哈的魔法咒语
题号：NC231634
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

魔法学院 CCNU 的新晋魔法师小哈正在练习课上学到的咒语。为了通过魔法学院的考试，小哈必须在一定时间内念完所有的咒语。
形式化的说，咒语可以认为是一个长度为 n 的字符串，记 为字符串 s 从 i 到 j 的子串。小哈在魔法考试中需要在 n 秒内每秒念一个咒语，念完字符串 s 的每一个前缀串 。

小哈念每个前缀串咒语 需要花费 v_i 的法力值，但由于这场考试是 CF 赛制(随着时间的流逝念咒语消耗的法力值会成倍变大)，第 k 秒念第 i 条咒语需要花费的法力值为 。

考试的主考官 先生还告诉小哈：对于，如果, 这条咒语要在 前被念完。形式化的讲： 如果记 这条咒语被念的时间为第 t_i 秒，小哈必须保证 。

小哈想知道他要通过考试的最小法力值消耗是多少。

输入描述:

第一行输入一个整数， n 表示咒语字符串的长度。 

第二行输入长为 n 的字符串表示咒语, 由小写字母组成。

第三行为 n 个整数，第 i 个整数代表念完第 i 个咒语所需法力值 v_i (。

输出描述:

输出一个整数表示小哈通过考试的最小法力值消耗。
示例1

输入

复制 
2 
ac
1 2

输出

复制 
4
示例2

输入

复制 
5 
aacaa
1 2 3 4 5

输出

复制 
50

说明

对于样例1：没有额外限制，小哈先念s[1, 2]，再念 s[1,1]。所需法力值为 2 * 1 + 1 * 2 = 4，可以证明 4 是小哈消耗的最小法力值。

对于样例2：有如下限制

s[1,1] 需要在 s[1,2] 前被念

s[1,1] 需要在 s[1,4] 前被念

s[1,1] 需要在 s[1,5] 前被念

s[1,2] 需要在 s[1,5] 前被念

小哈按如下顺序念：
s[1,3],s[1,1],s[1,4],s[1,2],s[1,5]，消耗法力为3 * 1 + 1 * 2 + 4 * 3 + 2 * 4 + 5 * 5 = 50
，可以证明 50 是小哈消耗的最小法力值。