#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; templatebool chmax(T &a, const T &b) {if(abool chmin(T &a, const T &b) {if(b struct PrimalDual{ struct edge{ int to; TF cap; TC cost; int rev; edge(){} edge(int to,TF cap,TC cost,int rev): to(to),cap(cap),cost(cost),rev(rev){} }; static const TC INF; vector> G; vector h,dist; vector prevv,preve; PrimalDual(){} PrimalDual(int n):G(n),h(n),dist(n),prevv(n),preve(n){} void add_edge(int u,int v,TF cap,TC cost){ G[u].emplace_back(v,cap,cost,G[v].size()); G[v].emplace_back(u,0,-cost,G[u].size()-1); } void dijkstra(int s){ struct P{ TC first; int second; P(TC first,int second):first(first),second(second){} bool operator<(const P&a) const{return a.first que; fill(dist.begin(),dist.end(),INF); dist[s]=0; que.emplace(dist[s],s); while(!que.empty()){ P p=que.top();que.pop(); int v=p.second; if(dist[v]0){ dijkstra(s); if(dist[t]==INF){ ok=0; return res; } for(int v=0;v<(int)h.size();v++) if(dist[v] const TC PrimalDual::INF = numeric_limits::max()/2; int n; string S; ll V[2010]; vector cs[4]; void solve(){ cin >> n; cin >> S; rep(i,n) cin >> V[i]; rep(i,n){ if(S[i]=='y') cs[0].push_back(i); if(S[i]=='u') cs[1].push_back(i); if(S[i]=='k') cs[2].push_back(i); if(S[i]=='i') cs[3].push_back(i); } if(cs[0].empty()){ cout << 0 << endl; return; } PrimalDual mcf(n+2); int pos[4]={0,0,0,0}; mcf.add_edge(n,cs[0][0],mod,0); rep(i,4){ rep(j,cs[i].size()-1){ mcf.add_edge(cs[i][j],cs[i][j+1],mod,0); } } rep(i,n){ if(S[i]=='y'){ pos[0]+=1; if(pos[1]>=0 && cs[1].size()>pos[1]) { mcf.add_edge(i,cs[1][pos[1]],1,-V[i]); } } if(S[i]=='u'){ pos[1]+=1; if(pos[2]>=0 && cs[2].size()>pos[2]) mcf.add_edge(i,cs[2][pos[2]],1,-V[i]); } if(S[i]=='k'){ pos[2]+=1; if(pos[3]>=0 && cs[3].size()>pos[3]) mcf.add_edge(i,cs[3][pos[3]],1,-V[i]); } if(S[i]=='i'){ pos[3]+=1; mcf.add_edge(i,n+1,1,-V[i]); } } mcf.add_edge(n,n+1,mod,0); int ok; //cout << 1 << endl; cout << -mcf.flow(n,n+1,2010,ok) << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }