简单字符串 - 代码源竞赛平台

题目描述

蜗蜗写了一道简单题的题面，它是长度为 $n$ 的小写英文字母串 $s$。如果能从题面中按原顺序挑出四个字符，组成 hard，这份题面就会被认为是困难题；否则是简单题。挑出的字符不必相邻，即 hard 是子序列，不要求是连续子串。

为了让题面保持简单，蜗蜗可以删除任意一些字符。删除原字符串第 $i$ 个字符会增加 $a_i$ 点歧义度；字符下标始终以原字符串为准，不因之前的删除而改变。

求删除后不再含有子序列 hard 时，所需增加的最小歧义度。允许不删除任何字符。

输入格式

第一行包含一个整数 $n$，表示字符串长度。

第二行包含一个长度为 $n$ 的小写英文字母串 $s$。

第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示删除每个原字符的代价。

输出格式

输出一行一个整数，表示使题面变为简单题的最小歧义度。

样例

4
hard
1 2 3 4

1

5
hhard
10 1 2 3 4

2

样例解释

样例 1 中，删除第 $1$ 个字符 h，花费 $1$，即可破坏 hard 子序列。

样例 2 中，删除第 $3$ 个字符 a，花费 $2$。只删除第二个 h 后，剩余字符串仍含有 hard，所以不能只花费 $1$。

数据范围

对于 100% 的数据，保证 $1\le n\le 10^5$，$s$ 长度为 $n$ 且只含小写英文字母，$1\le a_i\le 998244353$。