use std::cmp::min; const INF: isize = 1000000000000000000; fn main() { let (h, w): (usize, usize) = { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap() ) }; let mut dp = vec![vec![INF; w]; h-2]; for i in 0..h-2 { let a: Vec = { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|x| x.parse().unwrap()) .collect() }; for j in 0..w { if a[j] != -1 { dp[i][j] = a[j]; } } } for j in 1..w { for i in 0..h-2 { if dp[i][j] != INF { if h == 3 { dp[i][j] += dp[i][j-1]; } else if i == 0 { dp[i][j] += min(dp[i][j-1], dp[i+1][j-1]); } else if i == h-3 { dp[i][j] += min(dp[i-1][j-1], dp[i][j-1]); } else { dp[i][j] += min(dp[i][j-1], dp[i-1][j-1].min(dp[i+1][j-1])); } } } } let mut ans = INF; for i in 0..h-2 { ans = ans.min(dp[i][w-1]); } if ans == INF { println!("{}", -1); } else { println!("{}", ans); } }