#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let n = read::(); let s = read::(); let v = read_vec::(); let mut poses = vec![vec![]; 4]; for (i, ch) in s.chars().enumerate() { match ch { 'y' => poses[0].push(i), 'u' => poses[1].push(i), 'k' => poses[2].push(i), _ => poses[3].push(i), } } if poses.iter().any(|ref x| x.is_empty()) { println!("0"); return; } let mut flow = MinCostFlow::new(n + 2); flow.add_edge(n, poses[0][0], n as i32, 0); let inf: i64 = 10_0000_0000; for ci in 0..3 { for &pos in &poses[ci] { let search = poses[ci + 1].upper_bound(&pos); if search < poses[ci + 1].len() { flow.add_edge(pos, poses[ci + 1][search], 1, inf - v[pos]); } } } for ci in 0..4 { for i in 0..poses[ci].len() - 1 { flow.add_edge(poses[ci][i], poses[ci][i + 1], n as i32, 0); } } for &pos in &poses[3] { flow.add_edge(pos, n + 1, 1, inf - v[pos]); } let (cap, cost) = flow.flow(n, n + 1, n as i32); let ans = inf * 4 * cap as i64 - cost; println!("{}", ans); } pub trait BinarySearch { fn upper_bound(&self, x: &T) -> usize; } impl BinarySearch for [T] { fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } pub struct MinCostFlow { g: Vec>, } #[derive(Clone, Copy)] struct Edge { v: usize, rev: usize, cap: i32, cost: i64, } impl MinCostFlow { pub fn new(n: usize) -> Self { Self { g: vec![Vec::new(); n], } } pub fn add_edge(&mut self, u: usize, v: usize, cap: i32, cost: i64) { let rev_u = self.g[v].len(); let rev_v = self.g[u].len(); self.g[u].push(Edge { v, rev: rev_u, cap, cost, }); self.g[v].push(Edge { v: u, rev: rev_v, cap: 0, cost: -cost, }) } pub fn flow(&mut self, s: usize, t: usize, limit: i32) -> (i32, i64) { use std::cmp::Reverse; let n = self.g.len(); let mut flow = 0; let mut cost = 0; let mut p = vec![0; n]; let mut dist = vec![0; n]; let mut que = std::collections::BinaryHeap::new(); let mut prev = vec![(0, 0); n]; while flow < limit { dist.clear(); dist.resize(n, i64::max_value()); dist[s] = 0; que.push((Reverse(0), s)); prev[t].0 = !0; while let Some((Reverse(d), u)) = que.pop() { if dist[u] < d { continue; } for (i, e) in self.g[u].iter().enumerate() { let dd = d + e.cost - p[e.v] + p[u]; if e.cap > 0 && dd < dist[e.v] { dist[e.v] = dd; que.push((Reverse(dd), e.v)); prev[e.v] = (u, i); } } } if prev[t].0 == !0 { break; } for u in 0..n { if dist[u] != i64::max_value() { p[u] += dist[u]; } } let mut v = t; let mut add = limit - flow; while v != s { let (u, i) = prev[v]; add = add.min(self.g[u][i].cap); v = u; } flow += add; let mut v = t; while v != s { let (u, i) = prev[v]; let e = &mut self.g[u][i]; cost += e.cost * add as i64; e.cap -= add; let rev = e.rev; self.g[v][rev].cap += add; v = u; } } (flow, cost) } }