#include using namespace std; typedef long long ll; typedef pair p_ll; template void debug(T itr1, T itr2) { auto now = itr1; while(now=0; i--) const ll MOD = pow(10,9)+7; const ll LLINF = pow(2,61)-1; const int INF = pow(2,30)-1; vector fac; void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; } ll modpow(ll x, ll p) { ll result = 1, now = 1, pm = x; while (now<=p) { if (p&now) { result = result * pm % MOD; } now*=2; pm = pm*pm % MOD; } return result; } ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; } ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; } ll gcd(ll a, ll b) { if (a> adj; vector potential; vector minlen; MinCostFlow(ll n) { adj.resize(n); potential.resize(n); } void add_edge(ll from, ll to, ll cap, ll cost, ll idx = -1) { adj[from].push_back({to, cap, cost, (ll)adj[to].size(), idx, false}); adj[to].push_back({from, 0, -1*cost, (ll)adj[from].size()-1, idx, true}); } ll dijkstra(ll from, ll to) { ll N = adj.size(); auto c = [](const p_ll &x, const p_ll &y){return x.second>y.second;}; priority_queue, decltype(c)> q(c); minlen.assign(N,{LLINF,-1,-1}); minlen[from] = {0,-1,-1}; q.push(make_pair(from,0)); while(q.size()) { p_ll now = q.top(); q.pop(); ll np = now.first, nd = now.second; if (nd>minlen[np].d) continue; for (auto x: adj[np]) { if (x.cap==0||minlen[x.to].d<=minlen[np].d+x.cost) continue; q.push(make_pair(x.to, minlen[np].d+x.cost)); minlen[x.to] = {minlen[np].d+x.cost, np, adj[x.to][x.rev].rev}; } } return minlen[to].d; } ll dfs(ll from, ll to, ll flow) { if (from==to) return flow; auto &e = adj[minlen[to].from][minlen[to].pos]; ll f = dfs(from, minlen[to].from, min(flow, e.cap)); e.cap -= f; adj[e.to][e.rev].cap += f; return f; } ll calc(ll from, ll to, ll cost) { while(true) { if (cost==0||dijkstra(from, to)==LLINF) { ll result = 0; rep(i,adj.size()) { for (auto &x: adj[i]) { if (!x.isrev) { edge rev = adj[x.to][x.rev]; result += rev.cap * x.cost; } } } return cost==0 ? result : LLINF; } cost -= dfs(from, to, cost); } return 0; } void output() { rep(i,adj.size()) { for (auto &x: adj[i]) { if (!x.isrev) { edge rev = adj[x.to][x.rev]; cout << x.idx << ":" << i << "->" << x.to << " " << rev.cap << "/" << x.cap+rev.cap << endl; } } } } }; // ---------------------------------------------------------------------- // ---------------------------------------------------------------------- int main() { ll N; cin >> N; string S; cin >> S; ll V[N]; rep(i,N) cin >> V[i]; vector py, pu, pk, pi; rep(i,N) { if (S[i]=='y') py.push_back(i+1); if (S[i]=='u') pu.push_back(i+1); if (S[i]=='k') pk.push_back(i+1); if (S[i]=='i') pi.push_back(i+1); } // debug(all(py)); debug(all(pu)); debug(all(pk)); debug(all(pi)); MinCostFlow mcf(N+2); if (!py.size()) { cout << 0 << endl; return 0; } mcf.add_edge(0,py[0],INF,0); rep(i,py.size()-1) mcf.add_edge(py[i],py[i+1],INF,0); rep(i,pu.size()-1) mcf.add_edge(pu[i],pu[i+1],INF,0); rep(i,pk.size()-1) mcf.add_edge(pk[i],pk[i+1],INF,0); rep(i,pi.size()-1) mcf.add_edge(pi[i],pi[i+1],INF,0); for (auto x: py) { auto to = lower_bound(all(pu),x); if (to!=pu.end()) mcf.add_edge(x,*to,1,INF-V[x-1]); } for (auto x: pu) { auto to = lower_bound(all(pk),x); if (to!=pk.end()) mcf.add_edge(x,*to,1,INF-V[x-1]); } for (auto x: pk) { auto to = lower_bound(all(pi),x); if (to!=pi.end()) mcf.add_edge(x,*to,1,INF-V[x-1]); } for (auto x: pi) mcf.add_edge(x,N+1,1,INF-V[x-1]); ll result = 0; repr(i,1,N+1) { ll r = INF*i*4 - mcf.calc(0,N+1,1); result = max(result, r); } cout << result << endl; return 0; }