CF1096D.Easy Problem

Vasya is preparing a contest, and now he has written a statement for an easy problem. The statement is a string of length $n$ consisting of lowercase Latin latters. Vasya thinks that the statement can be considered hard if it contains a subsequence hard; otherwise the statement is easy. For example, hard, hzazrzd, haaaaard can be considered hard statements, while har, hart and drah are easy statements.

Vasya doesn't want the statement to be hard. He may remove some characters from the statement in order to make it easy. But, of course, some parts of the statement can be crucial to understanding. Initially the ambiguity of the statement is $0$, and removing $i$-th character increases the ambiguity by $a_i$ (the index of each character is considered as it was in the original statement, so, for example, if you delete character r from hard, and then character d, the index of d is still $4$ even though you delete it from the string had).

Vasya wants to calculate the minimum ambiguity of the statement, if he removes some characters (possibly zero) so that the statement is easy. Help him to do it!

Recall that subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

瓦西娅正在准备一场竞赛，现在他写好了一道简单题的题目描述。该题目描述是一个长度为 $n$ 的字符串，由小写拉丁字母组成。瓦西娅认为，如果该字符串中包含子序列 hard，则该题目描述是“难”的；否则就是“容易”的。例如，hard、hzazrzd、haaaaard 都可被视为“难”的题目描述，而 har、hart 和 drah 则是“容易”的题目描述。

瓦西娅不希望题目描述是“难”的。他可以通过删除字符串中的某些字符，使其变为“容易”的。当然，题目描述的某些部分可能对理解至关重要。初始时，题目描述的“歧义度”为 $0$；而删除第 $i$ 个字符会使歧义度增加 $a_i$（每个字符的索引按其在原字符串中的位置计算，例如：若先从 hard 中删除字符 r，再删除字符 d，则 d 的索引仍为 $4$，即使此时它已被从字符串 had 中删除）。

瓦西娅希望计算：在删除若干字符（可以为零个）使题目描述变为“容易”的前提下，所能达到的最小歧义度。请帮助他完成这一计算！

注意：子序列是指通过删除原序列中若干元素（不改变其余元素相对顺序）所得到的序列。

The first line contains one integer $n$ ($1 \le n \le 10^5$) — the length of the statement.

The second line contains one string $s$ of length $n$, consisting of lowercase Latin letters — the statement written by Vasya.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 998244353$).

第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 语句的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，由小写拉丁字母组成——这是瓦夏所写的语句。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 998244353$）。

Print minimum possible ambiguity of the statement after Vasya deletes some (possibly zero) characters so the resulting statement is easy.

在瓦西娅删除若干（可能为零）字符，使得最终的语句变得“简单”之后，输出该语句可能的最小歧义度。

In the first example, first two characters are removed so the result is ardh.

In the second example, $5$-th character is removed so the result is hhzawde.

In the third example there's no need to remove anything.

在第一个例子中，前两个字符被删除，因此结果为 ardh。

在第二个例子中，第 $5$ 个字符被删除，因此结果为 hhzawde。

在第三个例子中，无需删除任何字符。