Вася решил подготовить собсвенный контест и сейчас он разрабатывает самую простую задачу в нем. Условие задачи — это строка длины $$$n$$$, состоящая только из строчных букв латинского алфавита. Вася считает условие задачи сложным, если в нем есть подпоследовательность hard. В противном случае, условие задачи считается простым. Например, hard, hzazrzd, haaaaard — сложные условия, а har, hart and drah — простые условия.

Вася не хочет, чтобы условие его задачи было сложным. Он может удалить некоторые символы из своего условия. Но, конечно же, некоторые части условия являются важными для понимания. Изначально неоднозначность условия равно $$$0$$$, и удалив $$$i$$$-й символ Вася увеличит неоднозначность условия на $$$a_i$$$ (при этом индексы символов остаются такие же, как и в первоначально строке, например, если удалить символ r из строки hard, то индекс символа d останется $$$4$$$).

Вася хочет посчитать минимальное значение неоднозначности его условия, если он удалит какой-то набор символов (возможно пустой) так, что его условие станет простым. Помогите ему сделать это!