#[derive(Clone)] struct Edge { rev: usize, to: usize, cap: i64, } struct Graph { edge: Vec>, visited: Vec, } impl Graph { fn new(n: usize) -> Self { Self { edge: vec![vec![]; n], visited: vec![false; n], } } fn add_edge(&mut self, src: usize, dst: usize, cap: i64) { let dst_len = self.edge[dst].len(); let src_len = self.edge[src].len(); self.edge[src].push(Edge { rev: dst_len, to: dst, cap, }); self.edge[dst].push(Edge { rev: src_len, to: dst, cap: 0, }) } fn dfs(&mut self, pos: usize, goal: usize, flow: i64) -> i64 { if pos == goal { return flow; } self.visited[pos] = true; for i in 0..self.edge[pos].len() { let e = &self.edge[pos][i]; if e.cap == 0 || self.visited[e.to] { continue; } let flow = self.dfs(e.to, goal, std::cmp::min(flow, e.cap)); let e = &mut self.edge[pos][i]; if flow > 0 { e.cap -= flow; let e = e.clone(); self.edge[e.to][e.rev].cap += flow; return flow; } } return 0; } fn max_flow(&mut self, src: usize, dst: usize) -> i64 { let mut flow = 0; loop { self.visited = vec![false; self.visited.len()]; let f = self.dfs(src, dst, INF); if f == 0 { return flow; } flow += f; } } } const INF: i64 = 1_000_000_000_000_000; fn main() { let stdin = std::io::stdin(); let mut line = String::new(); stdin.read_line(&mut line).unwrap(); let line: Vec<&str> = line.split_whitespace().collect(); let n = line[0].parse::().unwrap(); let m = line[1].parse::().unwrap(); let mut line = String::new(); stdin.read_line(&mut line).unwrap(); let a: Vec<_> = line .split_whitespace() .map(|s| s.parse::().unwrap()) .collect(); let mut line = String::new(); stdin.read_line(&mut line).unwrap(); let b: Vec<_> = line .split_whitespace() .map(|s| s.parse::().unwrap()) .collect(); let mut g = Graph::new(n + m + 2); // 0: st // 1: ed for (i, &a) in a.iter().enumerate() { g.add_edge(0, 2 + i, a); } for (i, &b) in b.iter().enumerate() { g.add_edge(2 + n + i, 1, b); let mut line = String::new(); stdin.read_line(&mut line).unwrap(); let input: Vec<_> = line .split_whitespace() .map(|s| s.parse::().unwrap()) .collect(); for pos in &input[1..] { g.add_edge(2 + pos - 1, 2 + n + i, INF); } } println!("{}", b.iter().sum::() - g.max_flow(0, 1)); }