Vasya 正在准备一场比赛,现在他已经为一个简单的问题写了一份陈述。该语句是一个长度为 $$$n$$$ 的字符串,由小写拉丁字母组成。 Vasya 认为如果该语句包含一个子序列hard,则该语句可以被认为是hard;否则的话就很容易了。例如,hard、hzazrzd、haaaaard 可以被认为是硬语句,而 har、hart 和 drah 是简单语句。
Vasya 不希望声明变得困难。他可能会从声明中删除一些字符以使其变得简单。但是,当然,该声明的某些部分对于理解可能至关重要。最初语句的歧义性是 $$$0$$$,删除第 $$$i$$$ 个字符会使歧义性增加 $$$a_i$$$ (每个字符的索引被视为在原始语句中,因此,例如,如果您从 Hard 中删除字符 r,然后删除字符 d,则即使您从字符串 had 中删除它,d 的索引仍然是 $$$4$$$)。
Vasya 想要计算语句的最小歧义性,如果他删除一些字符(可能为零)以使语句变得简单。帮他做一下吧!
回想一下,子序列是可以通过删除一些元素而不改变剩余元素的顺序从另一个序列派生的序列。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 语句的长度。
第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由小写拉丁字母组成——这是Vasya写的语句。
第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 998244353$$$)。
输出
在 Vasya 删除一些(可能是零)字符后打印语句的最小可能歧义,以便生成的语句很容易。
示例
输入 #1
6 hhardh 3 2 9 11 7 1
输出 #1
5
输入 #2
8 hhzarwde 3 2 6 9 4 8 7 1
输出 #2
4
输入 #3
6 hhaarr 1 2 3 4 5 6
输出 #3
0
注意
在第一个示例中,前两个字符被删除,因此结果为 ardh。
在第二个示例中,删除了第 $$$5$$$ 个字符,因此结果为 hhzawde。
在第三个示例中,无需删除任何内容。