#![allow(unused_imports)] #![allow(non_snake_case, unused)] // ---------- begin input macro ---------- // https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254 より pub fn readln() -> String { let mut line = String::new(); ::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e)); line } macro_rules! read { ($($t:tt),*; $n:expr) => {{ let stdin = ::std::io::stdin(); let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| { let line = line.unwrap(); let mut it = line.split_whitespace(); _read!(it; $($t),*) }).collect::>(); ret }}; ($($t:tt),*) => {{ let line = readln(); let mut it = line.split_whitespace(); _read!(it; $($t),*) }}; } macro_rules! _read { ($it:ident; [char]) => { _read!($it; String).chars().collect::>() }; ($it:ident; [u8]) => { Vec::from(_read!($it; String).into_bytes()) }; ($it:ident; usize1) => { $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::().unwrap_or_else(|e| panic!("{}", e)) - 1 }; ($it:ident; [usize1]) => { $it.map(|s| s.parse::().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::>() }; ($it:ident; [$t:ty]) => { $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::>() }; ($it:ident; $t:ty) => { $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e)) }; ($it:ident; $($t:tt),+) => { ($(_read!($it; $t)),*) }; } // ---------- end input macro ---------- use std::cmp::*; use std::collections::*; use std::ops::*; use std::marker::*; const INF: i64 = std::i64::MAX/100; const MOD: i64 = 1_000_000_007; // const MOD: i64 = 998_244_353; fn main() { let (n,m) = read!(usize,usize); let mut a = vec![]; let mut edge = vec![vec![];n]; for i in 0..n { let (v,m) = read!(i64,usize); let b = read!([usize]); a.push(v); for &b in &b { edge[b-1].push(i); } } let mut dp = vec![vec![0;2];n]; for i in 0..n { dp[i][1] = -a[i]; } for v in 0..n { if v>0 { dp[v][0] = dp[v][0].max(dp[v-1][0]); } dp[v][0] = dp[v][0].max(dp[v][1]+a[v]); dp[v][1] = dp[v][1].max(dp[v][0]-a[v]); for &e in &edge[v] { dp[e][0] = dp[e][0].max(dp[v][0]); dp[e][1] = dp[e][1].max(dp[v][1]); } } let mut ans = 0; for i in 0..n { ans = ans.max(dp[i][0]); ans = ans.max(dp[i][1]+a[i]); } println!("{}",ans); }