use proconio::{input, marker::Usize1}; fn main() { input! { h: usize, w: usize, sx: Usize1, sy: Usize1, n: usize, xyc: [(Usize1, Usize1, i64); n], } let mut prev = (sx, sy); let mut dp = [0, -1]; for &(x, y, c) in &xyc { let mut ndp = [0, -1]; if dp[0] >= 0 && check((x, y), prev) { ndp[0] = ndp[0].max(dp[0] + c); } if dp[1] >= 0 { ndp[0] = ndp[0].max(dp[1] + c); } ndp[1] = ndp[1].max(dp[0]).max(dp[1]); dp = ndp; prev = (x, y); } let ans = dp.iter().max().unwrap(); println!("{ans}"); } fn check(now: (usize, usize), prev: (usize, usize)) -> bool { now.0 == prev.0 || now.1 == prev.1 || now.0 + now.1 == prev.0 + prev.1 || now.0 + prev.1 == prev.0 + now.1 }