/* -*- coding: utf-8 -*- * * 3597.cc: No.3597 Queen Score Attack 2 - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_N = 500000; const long long LINF = 1LL << 60; /* typedef */ using ll = long long; /* global variables */ ll dp[MAX_N + 1]; /* subroutines */ bool move(int x0, int y0, int x1, int y1) { return x0 == x1 || y0 == y1 || abs(x1 - x0) == abs(y1 - y0); } void setmax(ll &a, ll b) { if (a < b) a = b; } /* main */ int main() { int h, w, sx, sy, n; scanf("%d%d%d%d%d", &h, &w, &sx, &sy, &n); ll maxdp = -LINF; int px = sx, py = sy; for (int i = 0; i < n; i++) { int xi, yi, ci; scanf("%d%d%d", &xi, &yi, &ci); dp[i + 1] = maxdp + ci; if (move(px, py, xi, yi)) setmax(dp[i + 1], dp[i] + ci); setmax(maxdp, dp[i]); px = xi, py = yi; } ll maxsc = *max_element(dp, dp + n + 1); printf("%lld\n", maxsc); return 0; }