#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.1e9; struct MAX { int N; vector dat; MAX(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(); } int main() { int H, W, Q; cin >> H >> W >> Q; vector X(Q), Y(Q), Z(Q); vector DX{0, W + 1}, DY{0, H + 1}; rep(i, Q) { cin >> X[i] >> Y[i] >> Z[i]; DX.push_back(X[i]); DY.push_back(Y[i]); } DX = uniq(DX); DY = uniq(DY); MAX U(DX.size()); MAX D(DX.size()); MAX L(DY.size()); MAX R(DY.size()); vector nagasaU(DX.size(), 0); vector nagasaD(DX.size(), 0); vector nagasaL(DY.size(), 0); vector nagasaR(DY.size(), 0); // ha? rep(i, Q) { int x = doko(DX, X[i]); int y = doko(DY, Y[i]); tuple ans(INF, INF, INF); if (X[i] == 0) { // hidari auto sawaruU = [&]() -> tuple { int l = -1; int r = DX.size() - 1; while (r - l > 1) { int m = (l + r) / 2; (U.query(1, m) >= Y[i] ? r : l) = m; } return {DX[r], DX[r], 0}; }; auto sawaruD = [&]() -> tuple { int l = -1; int r = DX.size() - 1; while (r - l > 1) { int m = (l + r) / 2; (H + 1 - D.query(1, m) <= Y[i] ? r : l) = m; } return {DX[r], DX[r], H + 1}; }; auto sawaruR = [&]() -> tuple { return {W + 1 - nagasaR[y], W + 1, Y[i]}; }; ans = min({sawaruU(), sawaruD(), sawaruR()}); } else if (X[i] == W + 1) { // migi auto sawaruU = [&]() -> tuple { int l = 0; int r = DX.size(); while (r - l > 1) { int m = (l + r) / 2; (U.query(m, DX.size() - 1) >= Y[i] ? l : r) = m; } return {W + 1 - DX[l], DX[l], 0}; }; auto sawaruD = [&]() -> tuple { int l = 0; int r = DX.size(); while (r - l > 1) { int m = (l + r) / 2; (H + 1 - D.query(m, DX.size() - 1) <= Y[i] ? l : r) = m; } return {W + 1 - DX[l], DX[l], H + 1}; }; auto sawaruL = [&]() -> tuple { return {W + 1 - nagasaL[y], 0, Y[i]}; }; ans = min({sawaruU(), sawaruD(), sawaruL()}); } else if (Y[i] == 0) { // ue auto sawaruL = [&]() -> tuple { int l = -1; int r = DY.size() - 1; while (r - l > 1) { int m = (l + r) / 2; (L.query(1, m) >= X[i] ? r : l) = m; } return {DY[r], 0, DY[r]}; }; auto sawaruR = [&]() -> tuple { int l = -1; int r = DY.size() - 1; while (r - l > 1) { int m = (l + r) / 2; (H + 1 - R.query(1, m) <= Y[i] ? r : l) = m; } return {DY[r], W + 1, DY[r]}; }; auto sawaruD = [&]() -> tuple { return {H + 1 - nagasaD[x], X[i], H + 1}; }; ans = min({sawaruL(), sawaruR(), sawaruD()}); } else if (Y[i] == H + 1) { // sita auto sawaruL = [&]() -> tuple { int l = 0; int r = DY.size(); while (r - l > 1) { int m = (l + r) / 2; (L.query(m, DY.size() - 1) >= X[i] ? l : r) = m; } return {H + 1 - DY[l], 0, DY[l]}; }; auto sawaruR = [&]() -> tuple { int l = 0; int r = DY.size(); while (r - l > 1) { int m = (l + r) / 2; (W + 1 - R.query(m, DY.size() - 1) <= X[i] ? l : r) = m; } return {H + 1 - DY[l], W + 1, DY[l]}; }; auto sawaruU = [&]() -> tuple { return {H + 1 - nagasaU[x], X[i], 0}; }; ans = min({sawaruL(), sawaruR(), sawaruU()}); } else abort(); auto modosu = [&](int x, int y) { int ix = doko(DX, x); int iy = doko(DY, y); if (y == 0) { nagasaU[ix] = 0; U.update(ix, 0); } else if (y == H + 1) { nagasaD[ix] = 0; D.update(ix, 0); } else if (x == 0) { nagasaL[iy] = 0; L.update(iy, 0); } else if (x == W + 1) { nagasaR[iy] = 0; R.update(iy, 0); } else abort(); }; auto nobasu = [&]() { if (Y[i] == 0) { nagasaU[x] += Z[i]; if (nagasaU[x] >= get<0>(ans)) return false; U.update(x, nagasaU[x]); } else if (Y[i] == H + 1) { nagasaD[x] += Z[i]; if (nagasaD[x] >= get<0>(ans)) return false; D.update(x, nagasaD[x]); } else if (X[i] == 0) { nagasaL[y] += Z[i]; if (nagasaL[y] >= get<0>(ans)) return false; L.update(y, nagasaL[y]); } else if (X[i] == W + 1) { nagasaR[y] += Z[i]; if (nagasaR[y] >= get<0>(ans)) return false; R.update(y, nagasaR[y]); } return true; }; if (!nobasu()) { modosu(get<1>(ans), get<2>(ans)); modosu(X[i], Y[i]); } } ll ans = 0; rep(i, DY.size()) ans += nagasaL[i] + nagasaR[i]; rep(i, DX.size()) ans += nagasaU[i] + nagasaD[i]; cout << ans << endl; }