#include using namespace std; #define rep(i, n) for(int i = 0; i < n; i++) #define rep2(i, x, n) for(int i = x; i <= n; i++) #define rep3(i, x, n) for(int i = x; i >= n; i--) #define each(e, v) for(auto &e: v) #define pb push_back #define eb emplace_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)x.size() using ll = long long; using pii = pair; using pil = pair; using pli = pair; using pll = pair; #define pq(type, name) priority_queue name #define iq(type, name) priority_queue, greater> name const int inf = (1<<30)-1; const ll INF = (1LL<<60)-1; const double pi = acos(-1.0); const double EPS = 1e-10; template bool chmax(T &x, const T &y){ if(x < y) {x = y; return true;} return false; } template bool chmin(T &x, const T &y){ if(x > y) {x = y; return true;} return false; } void in() {} template void in(Head &&head, Tail &&...tail){ cin >> head; in(forward(tail)...); } void out() {cout << '\n';} template void out(Head &&head, Tail &&...tail){ cout << head << ' '; out(forward(tail)...); } void outn() {} template void outn(Head &&head, Tail &&...tail){ cout << head << '\n'; outn(forward(tail)...); } template void in(pair &p){ cin >> p.first >> p.second; } template void out(pair p){ cout << p.first << ' ' << p.second << '\n'; } using vi = vector; using vll = vector; #define vec1(type, name, ...) vector name(__VA_ARGS__) #define VEC1(type, ...) vector(__VA_ARGS__) #define vec2(type, name, a, ...) vector> name(a, VEC1(type, __VA_ARGS__)) #define VEC2(type, a, ...) vector>(a, VEC1(type, __VA_ARGS__)) #define vec3(type, name, a, b, ...) vector>> name(a, VEC2(type, b, __VA_ARGS__)) #define VEC3(type, a, b, ...) vector>>(a, VEC2(type, b, __VA_ARGS__)) #define vec4(type, name, a, b, c, ...) vector>>> name(a, VEC3(type, b, c, __VA_ARGS__)) #define VEC4(type, a, b, c, ...) vector>>>(a, VEC3(type, b, c, __VA_ARGS__)) #define vec5(type, name, a, b, c, d, ...) vector>>>> name(a, VEC4(type, b, c, d, __VA_ARGS__)) #define VEC5(type, a, b, c, d, ...) vector>>>>(a, VEC4(type, b, c, d, __VA_ARGS__)) template void vin(vector &a){ rep(i, sz(a)) cin >> a[i]; } template void vout(const vector &a){ for(auto &e: a) cout << e << ' '; cout << '\n'; } template void voutn(const vector &a){ for(auto &e: a) cout << e << '\n'; } template void unique(vector &a){ sort(all(a)), a.erase(unique(all(a)), a.end()); } vector iota(int n){ vector ret(n); iota(all(ret), 0); return ret; } template vector iota(const vector &a, bool greater = false){ vector ret = iota(sz(a)); sort(all(ret), [&](int i, int j){ return (a[i] < a[j])^greater; }); return ret; } struct io_setup{ io_setup(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; #define VEC(type, name, n) vector name(n); vin(name) #define INT(...) int __VA_ARGS__; in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; in(__VA_ARGS__) #define CHAR(...) char __VA_ARGS__; in(__VA_ARGS__) #define STR(...) string __VA_ARGS__; in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__; in(__VA_ARGS__) const int MOD = 1000000007; //const int MOD = 998244353; template struct Min_Cost_Flow{ struct edge{ int to; T cap, cost; int rev; edge(int to, T cap, T cost, int rev) : to(to), cap(cap), cost(cost), rev(rev) {} }; vector> es; vector d, h; vector pre_v, pre_e; const T INF_T; const int n; Min_Cost_Flow(int n) : INF_T(numeric_limits::max()), n(n){ es.resize(n), d.resize(n), h.resize(n), pre_v.resize(n), pre_e.resize(n); } void add_edge(int from, int to, T cap, T cost){ es[from].eb(to, cap, cost, sz(es[to])); es[to].eb(from, 0, -cost, sz(es[from])-1); } void bellman_ford(int s){ fill(all(h), INF_T); h[s] = 0; while(true){ bool update = false; rep(i, n){ if(h[i] == INF_T) continue; for(auto &e: es[i]){ if(e.cap > 0 && chmin(h[e.to], h[i]+e.cost)){ update = true; } } } if(!update) break; } } void dijkstra(int s){ fill(all(d), INF_T); using P = pair; priority_queue, greater

> que; que.emplace(d[s] = 0, s); while(!que.empty()){ T p; int i; tie(p, i) = que.top(); que.pop(); if(p > d[i]) continue; rep(j, sz(es[i])){ edge &e = es[i][j]; if(e.cap > 0 && chmin(d[e.to], d[i]+e.cost+h[i]-h[e.to])){ pre_v[e.to] = i, pre_e[e.to] = j; que.emplace(d[e.to], e.to); } } } } T min_cost_flow(int s, int t, T flow){ T ret = 0; bellman_ford(s); while(flow > 0){ dijkstra(s); if(d[t] == INF_T) return -1; rep(i, sz(es)){ if(h[i] == INF_T || d[i] == INF_T) h[i] = INF_T; else h[i] += d[i]; } T f = flow; for(int now = t; now != s; now = pre_v[now]){ chmin(f, es[pre_v[now]][pre_e[now]].cap); } ret += f*h[t], flow -= f; for(int now = t; now != s; now = pre_v[now]){ edge &e = es[pre_v[now]][pre_e[now]]; e.cap -= f, es[now][e.rev].cap += f; } } return ret; } }; int main(){ INT(N); STR(S); VEC(ll, V, N); Min_Cost_Flow G(N+2); int s = N, t = N+1; G.add_edge(s, t, 2000, 0); vi id[26]; rep(i, N){ if(S[i] == 'y') G.add_edge(s, i, INF, 0); if(S[i] == 'i') G.add_edge(i, t, 1, -V[i]); id[S[i]-'a'].eb(i); } rep(i, 26){ rep(j, sz(id[i])-1){ G.add_edge(id[i][j], id[i][j+1], INF, 0); } } string T = "yuki"; rep(i, 3){ each(e, id[T[i]-'a']){ if(id[T[i+1]-'a'].empty() || e > id[T[i+1]-'a'].back()) break; int u = *upper_bound(all(id[T[i+1]-'a']), e); G.add_edge(e, u, 1, -V[e]); } } out(-G.min_cost_flow(s, t, 2000)); }