use proconio::input; use std::cmp::min; const INF: isize = 1000000000000000000; fn main() { input!{ h: usize, w: usize } let mut dp = vec![vec![INF; w]; h-2]; for i in 0..h-2 { for j in 0..w { input!{ a: isize } if a != -1 { dp[i][j] = a; } } } for j in 1..w { for i in 0..h-2 { 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); } }