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.


-----Input-----

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$).


-----Output-----

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


-----Examples-----
Input
6
hhardh
3 2 9 11 7 1

Output
5

Input
8
hhzarwde
3 2 6 9 4 8 7 1

Output
4

Input
6
hhaarr
1 2 3 4 5 6

Output
0



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
input()
res_h = 0
res_ha = 0
res_har = 0
res_hard = 0
for s, a in zip(input(), list(map(int, input().split()))):
	if s == 'h':
		res_h += a
	elif s == 'a':
		res_ha = min(res_ha + a, res_h)
	elif s == 'r':
		res_har = min(res_har + a, res_ha)
	elif s == 'd':
		res_hard = min(res_hard + a, res_har)
print(res_hard)


import sys
input = sys.stdin.readline

n=int(input())
S=input()
A=list(map(int,input().split()))

DP=[0]*4#None,"h","ha","har"まででくいとめる
DP[0]=0

for i in range(n):
    if S[i]=="h":
        DP[0]+=A[i]
    elif S[i]=="a":
        DP[1]=min(DP[0],A[i]+DP[1])
    elif S[i]=="r":
        DP[2]=min(DP[1],A[i]+DP[2])
    elif S[i]=="d":
        DP[3]=min(DP[2],A[i]+DP[3])
        
print(min(DP))


n = int(input())
s = list(input())
a = list(map(int, input().split()))

dp = [1e20 for _ in range(4)]
dp[0] = 0
for i in range(n):
    if s[i] == 'h':
        dp[1] = min(dp[0], dp[1])
        dp[0] += a[i]
    elif s[i] == 'a':
        dp[2] = min(dp[1], dp[2])
        dp[1] += a[i]
    elif s[i] == 'r':
        dp[3] = min(dp[2], dp[3])
        dp[2] += a[i]
    elif s[i] == 'd':
        dp[3] += a[i]
ans = min(dp)
print(ans)


n = int(input())
s = input()
ar = list(map(int, input().split()))
dp = [[0, 0, 0, 0] for i in range(n + 1)]
for i in range(1, n + 1):
    if s[i - 1] == 'h':
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = dp[i - 1][2]
        dp[i][3] = dp[i - 1][3]
        dp[i][0] = dp[i - 1][0] + ar[i - 1]
    elif s[i - 1] == 'a':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = min(dp[i - 1][0], ar[i - 1] + dp[i - 1][1])
        dp[i][2] = dp[i - 1][2]
        dp[i][3] = dp[i - 1][3]
    elif s[i - 1] == 'r':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = min(dp[i - 1][1], ar[i - 1] + dp[i - 1][2])
        dp[i][3] = dp[i - 1][3]
    elif s[i - 1] == 'd':
        dp[i][0] = dp[i - 1][0]
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = dp[i - 1][2]
        dp[i][3] = min(dp[i - 1][2], ar[i - 1] + dp[i - 1][3])
    else:
        dp[i][1] = dp[i - 1][1]
        dp[i][2] = dp[i - 1][2]
        dp[i][3] = dp[i - 1][3]
        dp[i][0] = dp[i - 1][0]
print(dp[n][3])

#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        print(*args,  file=sys.stderr)
    dprint('debug mode')
except Exception:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()
#print(N)
S = input()

za = getIntList()
bbb = 10 ** 20
dp = [0,bbb,bbb,bbb]

for i in range(N):
    dp1 = dp.copy()
    c = S[i]
    w = za[i]
    if c == 'h':
        dp1[1] = min(dp1[1], dp1[0])
        dp1[0] += w
    elif c == 'a':
        dp1[2] = min(dp1[2], dp1[1])
        dp1[1] += w
    elif c == 'r':
        dp1[3] = min(dp1[3], dp1[2])
        dp1[2] += w
    elif c=='d':
        dp1[3] += w
    dp = dp1
    #dprint(dp)
print(min(dp))





n = int(input())
s = input()
a = [int(w) for w in input().split()]

hard = {'h': 1, 'a': 2, 'r': 3, 'd': 4}

cost = [10**20, 0, 0, 0, 0]

for ai, c in zip(a, s):
    if c in hard:
        cost[hard[c]] = min(cost[hard[c] - 1], cost[hard[c]] + ai)

print(cost[4])


import sys
def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

n = int(input())
s = input()
ambiguity = list(map(int, input().split()))

s_a = [y for y in list(zip([x for x in s], ambiguity)) if y[0] in "hard"]

if(len(s_a) < 4):
    print(0)
    quit()

l = len(s_a)+1
h = [0]*l
ha = [0]*l
har = [0]*l
hard = [0]*l

last_a = -1
last_r = -1
last_d = -1

for i, (c,a) in enumerate(s_a):
    if c == 'h':
        h[i] = a + h[i-1]
    else:
        h[i] = h[i-1]

    if c == 'a':
        ha[i] =  min(h[i],a+ha[last_a])
        last_a = i
    else:
        ha[i] = ha[i-1]

    if c == 'r':
        har[i] = min(ha[i], a+har[last_r])
        last_r = i
    else:
        har[i] = har[i-1]
    if c == 'd':
        hard[i] = min(har[i], a+hard[last_d])
        last_d = i
    else:
        hard[i] = hard[i-1]

eprint(h)
eprint(ha)
eprint(har)
eprint(hard)

print(hard[-2])





import sys

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()
a = list(map(int, sys.stdin.readline().strip().split()))

amb = 0
h = [0] * (n + 1)
ha = [0] * (n + 1)
har = [0] * (n + 1)
hard = [0] * (n + 1)

for i in range (1, n + 1):
    if s[i - 1] == 'h':
        h[i] = h[i - 1] + a[i - 1]
    else:
        h[i] = h[i - 1]
    if s[i - 1] == 'a':
        ha[i] = min([ha[i - 1] + a[i - 1], h[i - 1]])
    else:
        ha[i] = ha[i - 1]
    if s[i - 1] == 'r':
        har[i] = min([har[i - 1] + a[i - 1], ha[i - 1]])
    else:
        har[i] = har[i - 1]
    if s[i - 1] == 'd':
        hard[i] = min([hard[i - 1] + a[i - 1], har[i - 1]])
    else:
        hard[i] = hard[i - 1]

print(hard[n])

input()
dp = [0] * 5 
for i, c in zip(map('hard'.find, input()), map(int, input().split())) :
    if i < 0 : continue
    dp[i+1] = min(dp[i+1], dp[i])
    dp[i] += c
print(min(dp[:-1]))

n=int(input())
d=[0]*4
k=input()
g=list(map(int,input().split()))
for i in range(n):
    if('h'==k[i]):
        d[0]+=g[i]
    if('a'==k[i]):
        d[1]=min(d[0],d[1]+g[i])
    if('r'==k[i]):
        d[2]=min(d[1],d[2]+g[i])
    if('d'==k[i]):
        d[3]=min(d[2],d[3]+g[i])
print(min(d))


import math

n = int(input())
s = input()
A = [int(x) for x in input().split(' ')]

def f():
    dp = [[0]*5 for _ in [-1]*n]
    for i in reversed(range(n)):
        for hard in reversed(range(4)):
            if i+1 == n:
                temp1 = A[i]
                if s[i] == 'hard'[hard]:
                    if hard + 1 == 4:
                        temp2 = math.inf
                    else:
                        temp2 = 0
                else:
                    temp2 = 0
            else:
                temp1 = A[i] + dp[i+1][hard]
                if s[i] == 'hard'[hard]:
                    if hard + 1 == 4:
                        temp2 = math.inf
                    else:
                        temp2 = dp[i+1][hard+1]
                else:
                    temp2 = dp[i+1][hard]
            dp[i][hard] = min(temp1, temp2)
    return dp[0][0]

print(f())

input()
dp = [0] * 5 
for i, c in zip(map('hard'.find, input()), map(int, input().split())) :
    if i < 0 : continue
    dp[i+1] = min(dp[i+1], dp[i])
    dp[i] += c
    # print('hard'[i],dp)
print(min(dp[:-1]))

import sys
input = sys.stdin.readline

n = int(input())
s = input()
a = list(map(int, input().split()))

dp = [0] * 4

for i in range(n):
    if s[i] == 'h':
        dp[0] += a[i]
    elif s[i] == 'a':
        dp[1] = min(dp[0], a[i] + dp[1])
    elif s[i] == 'r':
        dp[2] = min(dp[1], a[i] + dp[2])
    elif s[i] == 'd':
        dp[3] = min(dp[2], a[i] + dp[3])

print(min(dp))

n = int(input())
s = input()
data = input().split()
a = [0 for i in range(n + 1)]
d = [[0 for i in range (5)] for j in range(n + 1)]
c = ['w', 'h', 'a', 'r', 'd']
for i in range(1, n + 1): 
	a[i] = int(data[i - 1])

s = '0' + s

for i in range (1, n + 1):
	if s[i] == c[1]:
		d[i][1] = d[i - 1][1] + a[i]
	else: d[i][1] = d[i - 1][1]

for j in range (2, 5):
	for i in range(1, n + 1):
		if s[i] == c[j]:
			d[i][j] = min(d[i - 1][j - 1], d[i - 1][j] + a[i])
		else: d[i][j] = d[i - 1][j]

print(d[n][4])

lens = int(input())
res_h, res_a, res_r, res_d = 0, 0, 0, 0
for ch, amb in zip(input(), [int(x) for x in input().split()]):
    if    ch == "h": res_h += amb
    elif  ch == "a": res_a  = min(res_a + amb, res_h)
    elif  ch == "r": res_r  = min(res_r + amb, res_a)
    elif  ch == "d": res_d  = min(res_d + amb, res_r)
print(res_d)


n = int(input())
S = input()
A = [int(i) for i in input().split()]

INF = 10 ** 15
T = 'hard'
dp = [[INF] * (n+1) for i in range(5)]

for i in range(5):
    dp[i][0] = 0

for i, s in enumerate(S):
    for j, t in enumerate('hard'):
        if s == t:
            dp[j][i+1] = min(dp[j][i+1], dp[j][i] + A[i])
            dp[j+1][i+1] = min(dp[j+1][i+1], dp[j][i])
        else:
            dp[j][i+1] = min(dp[j][i+1], dp[j][i])

print(min(dp[i][n] for i in range(4)))

n = int(input())
a, b, c, d = 0, 0, 0, 0
for s, x in zip(input(), list(map(int, input().split()))):
    if(s =='h'):  a = a + x;
    if(s =='a'):  b = min(a ,b + x)
    if(s =='r'):   c = min(b, c + x)
    if(s =='d'):  d = min(c, d + x)
print(d)


#!/usr/bin/env python
# coding: utf-8

# In[22]:

n=int(input())
word=list(input())

costs=list(map(int, input().rstrip().split()))


# In[23]:


costlist=[0]*4

for i in range(n):
    
    if word[i]=='h':
        costlist[0]+=costs[i]
    
    if word[i]=='a':
        costlist[1]=min(costlist[0],costlist[1]+costs[i])
        
    if word[i]=='r':
        costlist[2]=min(costlist[1],costlist[2]+costs[i])
        
        
    if word[i]=='d':    
        costlist[3]=min(costlist[2],costlist[3]+costs[i])


# In[25]:


print(costlist[3])


# In[ ]:






n = int(input())
s = input()
t = 'hard'
a = list(map(int, input().split()))
dp = [x[:] for x in [[0]*4]*(n+1)]
for i in range(1,n+1):
    for j in range(4):
        if s[i-1] == t[j]:
            if j ==0:
                dp[i][j] = dp[i-1][j]+a[i-1]
            else:
                dp[i][j] = min(dp[i-1][j]+a[i-1], dp[i-1][j-1])
        else:
            dp[i][j] = dp[i-1][j]
res = float('inf')
for i in range(4):
    res = min(res, dp[n][i])
print(res)


_ = input()
s = input()
a = list(map(int, input().split()))

hard = "hard"

dp = [0]*4
for i in range(len(s)):
    if s[i] == hard[0]:
        dp[0] += a[i]
    for j in range(1, 4):
        if s[i] == hard[j]:
            # If same letter, either leave as-is (extend prefix) or remove it
            dp[j] = min(dp[j-1], dp[j] + a[i])

print(min(dp))


# I/p
# 6
# baabbb
# o/p
# bab
#
# n=int(input())
# data=input()
# val=0
# i=1
# s=""
# while val!=n:
#     s+=data[val]
#     val+=i
#     i+=1
# print(s)

#I/p
# 4
# 1 3 3 7
#O/p
# 2
# n=int(input())
# data=list(map(int,input().split()))
# data1=max(data)
# data.remove(max(data))
# a= max(data)-min(data)
# data.append(data1)
# data2=min(data)
# data.remove(min(data))
# b=max(data)-min(data)
# if a>b:
#     print(b)
# else: print(a)


#Find Divisible
# n=int(input())
# while n>0:
#     a,b=map(int,input().split())
#     while a<=b:
#         if b%a==0:
#             print(a,b)
#             break
#         b-=1
#     n-=1
# for _ in [0]*int(input()):l=int(input().split()[0]);print(l,2*l)


n = int(input())
s = input()
a =list(map(int,input().split()))

hard = {'h': 1, 'a': 2, 'r': 3, 'd': 4}

cost = [10**20, 0, 0, 0, 0]

for ai, c in zip(a, s):
    if c in hard:
        cost[hard[c]] = min(cost[hard[c] - 1], cost[hard[c]] + ai)

print(cost[4])

n=int(input())
s=list(input())
c=list(map(int,input().split()))
h=a=r=d=0
for i in range(n):
    if s[i]=='h':
        h+=c[i]
    elif s[i]=='a':
        a=min(h,a+c[i])
    elif s[i]=='r':
        r=min(a,r+c[i])
    elif s[i]=='d':
        d=min(r,d+c[i])
print(d)

l=int(input())
s = input()
arr=list(map(int, input().split()))
hard = "hard"
dp=[0]*4
for i in range(l):
	if s[i]==hard[0]:
		dp[0]+=arr[i]
	for j in range(1,4):
		if s[i]==hard[j]:
			dp[j]=min(dp[j-1],dp[j]+arr[i])
print(min(dp))


import math

n = int(input())
s = input()
c = list(map(int, input().split()))

h = [0]*n
ta = 0
tr = 0
td = 0
for i in range(n):
    if s[i]=='h':
        h[i] = c[i]
    if(i):
        h[i] = h[i] + h[i-1]
    if s[i]=='a':
        ta = min(ta+c[i], h[i])
    elif s[i]=='r':
        tr = min(tr+c[i], ta)
    elif s[i]=='d':
        td = min(td+c[i], tr)
      
print(td)


n = int(input())
s = input()
dp = [0] * 4
a = list(map(int, input().split()))
for i in range(len(s)):
    if s[i] == "h":
        dp[0] += a[i]
    elif s[i] == "a":
        dp[1] = min(dp[0], dp[1] + a[i])
    elif s[i] == "r":
        dp[2] = min(dp[1], dp[2] + a[i])
    elif s[i] == "d":
        dp[3] = min(dp[2], dp[3] + a[i])

print(min(dp))