#include #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) using namespace std; using ll = long long; const int INF = 1.01e9; struct Kitune { int N; vector dat; Kitune(int n) { N = 1; while (N < n) N *= 2; dat.resize(N * 2, -INF); } void update(int k, int v) { k += N; dat[k] = v; while (k > 1) { k >>= 1; dat[k] = max(dat[k * 2], dat[k * 2 + 1]); } } int query(int l, int r) { l += N; r += N; int res = -INF; while (l <= r) { if ((l & 1) == 1) res = max(res, dat[l++]); if ((r & 1) == 0) res = max(res, dat[r--]); l >>= 1; r >>= 1; } return res; } }; vector uniq(vector a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); return a; } int doko(const vector &a, int x) { return lower_bound(a.begin(), a.end(), x) - a.begin(); } template ostream &operator<<(ostream &o, tuple t) { return o << '(' << get<0>(t) << ',' << get<1>(t) << ','<< get<2>(t) << ')'; } int main() { int H, W, Q; cin >> H >> W >> Q; vector X(Q), Y(Q), Z(Q); vector> zisyo{{0, H + 1}, {0, W + 1}}; rep(i, Q) { cin >> X[i] >> Y[i] >> Z[i]; zisyo[0].push_back(Y[i]); zisyo[0].push_back(H + 1 - Y[i]); zisyo[1].push_back(X[i]); zisyo[1].push_back(W + 1 - X[i]); } zisyo[0] = uniq(zisyo[0]); zisyo[1] = uniq(zisyo[1]); zisyo.emplace_back(); zisyo.emplace_back(); for (int x : zisyo[0]) zisyo[2].push_back(H + 1 - x); for (int x : zisyo[1]) zisyo[3].push_back(W + 1 - x); reverse(zisyo[2].begin(), zisyo[2].end()); reverse(zisyo[3].begin(), zisyo[3].end()); vector ktn; vector> nagasa; rep(i, 4) ktn.emplace_back(zisyo[i].size()); rep(i, 4) nagasa.emplace_back(zisyo[i].size()); rep(i, Q) { int k, z; if (X[i] == 0) { k = 0; z = Y[i]; } else if (Y[i] == 0) { k = 1; z = W + 1 - X[i]; } else if (X[i] == W + 1) { k = 2; z = H + 1 - Y[i]; } else if (Y[i] == H + 1) { k = 3; z = X[i]; } else abort(); auto hidarite = [&]() -> tuple { int butukaru = 0; int butukaranai = zisyo[(k + 1) % 4].size() - 1; while (butukaranai - butukaru > 1) { int aida = (butukaru + butukaranai) / 2; if (ktn[(k + 1) % 4].query(aida, zisyo[(k + 1) % 4].size() - 1) >= z) { butukaru = aida; } else { butukaranai = aida; } } return {zisyo[(k + 1) % 4].back() - zisyo[(k + 1) % 4][butukaru], 1, butukaru}; }; auto migite = [&]() -> tuple { int butukaru = zisyo[(k + 3) % 4].size() - 1; int butukaranai = 0; while (butukaru - butukaranai > 1) { int aida = (butukaru + butukaranai) / 2; if (ktn[(k + 3) % 4].query(0, aida) >= zisyo[k].back() - z) { butukaru = aida; } else { butukaranai = aida; } } return {zisyo[(k + 3) % 4][butukaru], 3, butukaru}; }; auto mukai = [&]() -> tuple { int s = doko(zisyo[(k + 2) % 4], zisyo[k].back() - z); return {zisyo[(k + 1) % 4].back() - nagasa[(k + 2) % 4][s], 2, s}; }; auto hazime_ni_butukaru = min({hidarite(), migite(), mukai()}); int zi = doko(zisyo[k % 2], z); auto kakikae = [&](int k, int z, int v) { k %= 4; nagasa[k][z] = v; ktn[k].update(z, v); }; kakikae(k, zi, nagasa[k][zi] + Z[i]); if (nagasa[k][zi] >= get<0>(hazime_ni_butukaru)) { kakikae(k, zi, 0); kakikae(k + get<1>(hazime_ni_butukaru), get<2>(hazime_ni_butukaru), 0); } } ll ans = 0; rep(i, 4) for (int x : nagasa[i]) ans += x; cout << ans << endl; }