use proconio::input; fn main() { input! { n:usize, a:[[usize;3];n], } const M: usize = 5000; const INF: i64 = std::i64::MAX; let mut dp = vec![vec![0; 3]; M + 1]; for i in 1..=M { for j in 0..3 { dp[i][j] = -INF; } } for i in 0..n { let mut ndp = vec![vec![-INF; 3]; M + 1]; for j in 0..=M { for k in 0..3 { if dp[j][k] == -INF { continue; } for l in 0..3 { if k == l { continue; } let atk = j + a[i][l] as usize; if M < atk { let over = (atk - M) * (n - i); ndp[M - 1][l] = ndp[M - 1][l].max(dp[j][k] + M as i64 + over as i64); } else { let nj = atk.saturating_sub(1); ndp[nj][l] = ndp[nj][l].max(dp[j][k] + atk as i64); } } } } dp = ndp; } let mut ans = 0; for i in 0..=M { for j in 0..3 { ans = ans.max(dp[i][j]); } } println!("{}", ans); }