#include #include #include #include #include #include #include #include #define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl; #define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; typedef long long ll; const ll INF = 1e18; struct edge{ int to; ll cap, cost; int rev; }; class MinCostFlow{ public: int V; // 頂点数 vector> G; MinCostFlow(int v){ V = v; G = vector>(v, vector()); dist = vector(v); preve = vector(v); prevv = vector(v); } void add_edge(int from, int to, ll cap, ll cost){ G[from].push_back((edge){to, cap, cost, G[to].size()}); G[to].push_back((edge){from, 0, -cost, G[from].size()-1}); } ll min_cost_flow(int s, int t, int f){ ll res = 0; while(f > 0){ fill(dist.begin(), dist.end(), INF); dist[s] = 0; for(int v = 0; v < V; v++){ for(int i = 0; i < G[v].size(); i++){ edge &e = G[v][i]; if(e.cap > 0 && dist[e.to] > dist[i]+e.cost){ dist[e.to] = dist[v]+e.cost; prevv[e.to] = v; preve[e.to] = i; } } } if(dist[t] == INF){ return -1; } ll d = f; for(int v = t; v != s; v = prevv[v]){ d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += d*dist[t]; for(int v = t; v != s; v = prevv[v]){ edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } private: vector dist; vector prevv, preve; }; int n; string s; ll v[2000]; void input(){ cin >> n >> s; for(int i = 0; i < n; i++) cin >> v[i]; } int idx_from(int i){ return i+1; } int idx_to(int i){ return i+n+1; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; input(); MinCostFlow mcf(2*n+2); int f = 0, t = 2*n+1; int cnty = 0; for(int i = 0; i < n; i++){ mcf.add_edge(idx_from(i), idx_to(i), 1, 0); if(s[i] == 'y'){ cnty++; mcf.add_edge(0, idx_from(i), 1, 0); mcf.add_edge(idx_to(i), t, 1, 0); } if(s[i] == 'i'){ mcf.add_edge(idx_to(i), t, 1, -v[i]); } for(int j = i+1; j < n; j++){ bool find_same = false; bool find_after = false; if(!find_after){ if(s[i] == 'y' && s[j] == 'u'){ mcf.add_edge(idx_to(i), idx_from(j), 1, -v[i]); find_after = true; } if(s[i] == 'u' && s[j] == 'k'){ mcf.add_edge(idx_to(i), idx_from(j), 1, -v[i]); find_after = true; } if(s[i] == 'k' && s[j] == 'i'){ mcf.add_edge(idx_to(i), idx_from(j), 1, -v[i]); find_after = true; } } if(!find_same){ if(s[i] == s[j]){ mcf.add_edge(idx_to(i), idx_from(j), 1, 0); find_same = true; } } } } cout << -mcf.min_cost_flow(f, t, cnty) << endl; }