struct Info { k: usize, c: i64, v: Vec<(usize, i64)>, } struct Input { n: usize, m: i64, info: Vec, } fn main() { let Input { n, m, info } = Input::read(std::io::stdin().lock()); assert!(matches!(n, 1..=100)); assert!(matches!(m, 0..=1_000_000_000)); assert_eq!(n, info.len()); for (i, Info { k, c, v }) in info.iter().enumerate() { assert!(*k < n); assert!(matches!(c, 0..=1_000_000_000)); assert_eq!(*k, v.len()); for (a, b) in v { assert!(*a < n); assert!(*a != i); assert!(matches!(b, 0..=1_000_000_000)); } assert!(v.windows(2).all(|x| x[0].0 < x[1].0)); } let mut ans = 0; for i in 0i64..1 << n { let mut tmp = m * i.count_ones() as i64; for (j, Info { c, .. }) in info.iter().enumerate() { if i >> j & 1 == 1 { tmp -= c; } } for (j, Info { v, .. }) in info.iter().enumerate() { if i >> j & 1 == 1 { for (a, b) in v { if i >> a & 1 == 1 { tmp += b; } } } } ans = ans.max(tmp); } println!("{}", ans); } impl Input { fn read(mut input: T) -> Input { let (n, m) = { let mut buffer = String::new(); input.read_line(&mut buffer).unwrap(); match &split(&buffer).unwrap()[..] { [n, m] => (n.parse().unwrap(), m.parse().unwrap()), _ => panic!("input format error: N M"), } }; let info = { let mut info = Vec::with_capacity(n); for _ in 0..n { let mut buffer = String::new(); input.read_line(&mut buffer).unwrap(); let (k, c) = match &split(&buffer).unwrap()[..] { [k, c] => (k.parse().unwrap(), c.parse().unwrap()), _ => panic!("input format error: k C"), }; let v = if k == 0 { Vec::new() } else { let mut a = String::new(); input.read_line(&mut a).unwrap(); let a = split(&a).unwrap(); let mut b = String::new(); input.read_line(&mut b).unwrap(); let b = split(&b).unwrap(); let v = a .iter() .zip(&b) .map(|(x, y)| (x.parse::().unwrap() - 1, y.parse().unwrap())) .collect(); v }; info.push(Info { k: k, c: c, v: v }); } info }; Input { n: n, m: m, info: info, } } } fn split(s: &str) -> Option> { enum State { Word(usize), Space, End, } let mut state = State::Word(0); let mut ret = Vec::new(); for (i, c) in s.char_indices() { let prev = match state { State::End => return None, State::Word(i) => i, State::Space => { state = State::Word(i); i } }; if c == ' ' || c == '\n' { ret.push(&s[prev..i]); state = if c == ' ' { State::Space } else { State::End }; } } matches!(state, State::End).then(|| ret) }