CF1096D Easy Problem

Vasya 正在准备一场比赛，现在他已经为一道简单题写好了题面。题面是一个长度为 $n$ 的字符串，由小写拉丁字母组成。Vasya 认为，如果题面中包含子序列 hard，则该题面可以被认为是困难的；否则，该题面就是简单的。例如，hard、hzazrzd、haaaaard 都可以被认为是困难的题面，而 har、hart 和 drah 则是简单的题面。 Vasya 不希望题面变得困难。他可以删除题面中的一些字符，使其变为简单的题面。当然，题面中的某些部分可能对理解很重要。最初，题目的“歧义度”为 $0$，删除第 $i$ 个字符会使歧义度增加 $a_i$（每个字符的下标以原始字符串为准，例如，如果你从 hard 中删除字符 r，再删除字符 d，d 的下标仍然是 $4$，即使你是从 had 中删除的）。 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 删除一些（可能为零）字符后，使题面变为简单题面时，最小可能的歧义度。

在第一个样例中，前两个字符被删除，结果为 ardh。 在第二个样例中，第 $5$ 个字符被删除，结果为 hhzawde。 在第三个样例中，无需删除任何字符。 由 ChatGPT 4.1 翻译