use proconio::input; fn main() { input! { n:usize, a:[[usize;3];n], } let mut dp = vec![[(0, 0); 3]; n]; for i in 0..3 { dp[0][i] = (a[0][i], a[0][i].saturating_sub(1)); } for i in 1..n { for j in 0..3 { for k in 0..3 { if j == k { continue; } if dp[i][k].0 < dp[i - 1][j].0 + dp[i - 1][j].1 + a[i][k] { dp[i][k].0 = dp[i - 1][j].0 + dp[i - 1][j].1 + a[i][k]; dp[i][k].1 = (dp[i - 1][j].1 + a[i][k]).saturating_sub(1); } } } } let ans = dp[n - 1][0].0.max(dp[n - 1][1].0).max(dp[n - 1][2].0); println!("{}", ans); }