#include using namespace std; template< typename flow_t, typename cost_t > struct PrimalDual { const cost_t INF; struct edge { int to; flow_t cap; cost_t cost; int rev; bool isrev; }; vector< vector< edge > > graph; vector< cost_t > potential, min_cost; vector< int > prevv, preve; PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {} void add_edge(int from, int to, flow_t cap, cost_t cost) { graph[from].emplace_back((edge) {to, cap, cost, (int) graph[to].size(), false}); graph[to].emplace_back((edge) {from, 0, -cost, (int) graph[from].size() - 1, true}); } cost_t min_cost_flow(int s, int t, flow_t f) { int V = (int) graph.size(); cost_t ret = 0; using Pi = pair< cost_t, int >; priority_queue< Pi, vector< Pi >, greater< Pi > > que; potential.assign(V, 0); preve.assign(V, -1); prevv.assign(V, -1); while(f > 0) { min_cost.assign(V, INF); que.emplace(0, s); min_cost[s] = 0; while(!que.empty()) { Pi p = que.top(); que.pop(); if(min_cost[p.second] < p.first) continue; for(int i = 0; i < graph[p.second].size(); i++) { edge &e = graph[p.second][i]; cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to]; if(e.cap > 0 && min_cost[e.to] > nextCost) { min_cost[e.to] = nextCost; prevv[e.to] = p.second, preve[e.to] = i; que.emplace(min_cost[e.to], e.to); } } } if(min_cost[t] == INF) return -1; for(int v = 0; v < V; v++) potential[v] += min_cost[v]; flow_t addflow = f; for(int v = t; v != s; v = prevv[v]) { addflow = min(addflow, graph[prevv[v]][preve[v]].cap); } f -= addflow; ret += addflow * potential[t]; for(int v = t; v != s; v = prevv[v]) { edge &e = graph[prevv[v]][preve[v]]; e.cap -= addflow; graph[v][e.rev].cap += addflow; } } return ret; } void output() { for(int i = 0; i < graph.size(); i++) { for(auto &e : graph[i]) { if(e.isrev) continue; auto &rev_e = graph[e.to][e.rev]; cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl; } } } }; int main() { int N; cin >> N; string S; cin >> S; vector< int > V(N); for(auto &v : V) cin >> v; PrimalDual< int64_t, int64_t > flow(N + N + N + 2); int X = N + N + N; int Y = X + 1; for(int i = 1; i < N; i++) { flow.add_edge(i - 1, i, flow.INF, 0); flow.add_edge(i - 1 + N, i + N, flow.INF, 0); flow.add_edge(i - 1 + N + N, i + N + N, flow.INF, 0); } for(int i = 0; i < N; i++) { if(S[i] == 'y') { flow.add_edge(X, i, 1, -V[i]); } else if(S[i] == 'u') { flow.add_edge(i, i + N, 1, -V[i]); } else if(S[i] == 'k') { flow.add_edge(i + N, i + N + N, 1, -V[i]); } else { flow.add_edge(i + N + N, Y, 1, -V[i]); } } flow.add_edge(X, Y, flow.INF, 0); cout << -flow.min_cost_flow(X, Y, flow.INF) << "\n"; }