#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{ const E inf=numeric_limits::max(); struct edge{ int to,rev; T cap; E cost; edge(int to,T cap,E cost,int rev):to(to),cap(cap),cost(cost),rev(rev){} }; vector> G; vector> pos; vector h,dist; vector prevv,preve; PrimalDual(int n):G(n),h(n),dist(n),prevv(n),preve(n){} int add_edge(int from,int to,T cap,E cost){ pos.emplace_back(from,G[from].size()); G[from].emplace_back(to,cap,cost,G[to].size()); G[to].emplace_back(from,0,-cost,G[from].size()-1); return pos.size()-1; } tuple get_edge(int i){ auto e=G[pos[i].first][pos[i].second]; auto re=G[e.to][e.rev]; return {pos[i].first,e.to,e.cap+re.cap,re.cap,e.cost}; } vector> edges(){ vector> res; for (int i=0;irhs.c;} }; priority_queue

pq; fill(dist.begin(),dist.end(),inf); dist[s]=0; pq.emplace(dist[s],s); while(!pq.empty()){ auto p=pq.top(); pq.pop(); int v=p.v; if (dist[v]0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){ dist[e.to]=dist[v]+e.cost+h[v]-h[e.to]; prevv[e.to]=v; preve[e.to]=i; pq.emplace(dist[e.to],e.to); } } } } vector> slope(int s,int t,T lim){ T f=0; E c=0,pre=-1; vector> res; res.emplace_back(f,c); while(f min_cost_max_flow(int s,int t){ return slope(s,t,numeric_limits::max()).back(); } vector> min_cost_slope(int s,int t){ return slope(s,t,numeric_limits::max()); } }; 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); } rep(i,4) if(cs[i].empty()){ cout << 0 << endl; return; } PrimalDual mcf(n+2); int pos[4]={0,0,0,0}; mcf.add_edge(n,cs[0][0],4010,0); rep(i,4){ rep(j,cs[i].size()-1){ mcf.add_edge(cs[i][j],cs[i][j+1],4010,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,4010,0); int ok; //cout << 1 << endl; cout << -mcf.min_cost_flow(n,n+1,2010) << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }