#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; typedef int FLOW; // フローを表す型、今回は int 型 typedef int COST; // コストを表す型、今回は int 型 const int MAX_V = 100; // グラフの最大ノード数 const COST INF = 100000000; // 十分大きい値 // グラフの辺の構造体 struct Edge { int rev, from, to; FLOW cap, icap; COST cost; Edge(int r, int f, int t, FLOW ca, COST co) : rev(r), from(f), to(t), cap(ca), icap(ca), cost(co) {} }; // グラフ構造体 struct Graph { int V; vector list[MAX_V]; Graph(int n = 0) : V(n) { for (int i = 0; i < MAX_V; ++i) list[i].clear(); } void init(int n = 0) { V = n; for (int i = 0; i < MAX_V; ++i) list[i].clear(); } void resize(int n = 0) { V = n; } void reset() { for (int i = 0; i < V; ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; } inline vector& operator [] (int i) { return list[i]; } Edge &redge(Edge &e) { if (e.from != e.to) return list[e.to][e.rev]; else return list[e.to][e.rev + 1]; } void addedge(int from, int to, FLOW cap, COST cost) { list[from].push_back(Edge((int)list[to].size(), from, to, cap, cost)); list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0, -cost)); } }; // 最小費用流を求める関数 COST MinCostFlow(Graph &G, int s, int t, FLOW inif) { COST dist[MAX_V]; int prevv[MAX_V]; int preve[MAX_V]; COST res = 0; FLOW f = inif; while (f > 0) { fill(dist, dist + G.V, INF); dist[s] = 0; while (true) { bool update = false; for (int v = 0; v < G.V; ++v) { if (dist[v] == INF) continue; for (int i = 0; i < G[v].size(); ++i) { Edge &e = G[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; prevv[e.to] = v; preve[e.to] = i; update = true; } } } if (!update) break; } if (dist[t] == INF) return 0; FLOW d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } f -= d; res += dist[t] * d; for (int v = t; v != s; v = prevv[v]) { Edge &e = G[prevv[v]][preve[v]]; Edge &re = G.redge(e); e.cap -= d; re.cap += d; } } return res; } 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(); Graph mcf(2*n+2); int f = 0, t = 2*n+1; int cnty = 0; for(int i = 0; i < n; i++){ mcf.addedge(idx_from(i), idx_to(i), 1, 0); if(s[i] == 'y'){ cnty++; mcf.addedge(0, idx_from(i), 1, 0); mcf.addedge(idx_to(i), t, 1, 0); } if(s[i] == 'i'){ mcf.addedge(idx_to(i), t, 1, -v[i]); } for(int j = i+1; j < n; j++){ if(s[i] == 'y' && s[j] == 'u'){ mcf.addedge(idx_to(i), idx_from(j), 1, -v[i]); } if(s[i] == 'u' && s[j] == 'k'){ mcf.addedge(idx_to(i), idx_from(j), 1, -v[i]); } if(s[i] == 'k' && s[j] == 'i'){ mcf.addedge(idx_to(i), idx_from(j), 1, -v[i]); } } } cout << -MinCostFlow(mcf, f, t, cnty) << endl; }