#include #include #include #include using namespace std;

const int N = 1005; const int dx[5] = {0, 0, 0, 1, -1}, dy[5] = {1, -1, 0, 0, 0}; int dp[1 << 20]; int fish[N][N]; // fish[x][y]：(x,y)处鱼的编号 int c[11]; // 第i个位置的fish数量 vector<pair<int, int>> bombPos; // 应该放炸弹的位置

int main() { int n, m, k; cin >> n >> m >> k; int x, y, s = 0; for (int i = 1; i <= k; i++) { cin >> x >> y >> c[i]; s <<= 2, s |= c[i]; fish[x][y] = i; // 预处理应该放炸弹的位置 for (int t = 0; t < 5; t++) { int newx = x + dx[t], newy = y + dy[t]; if (newx > 0 && newy > 0 && newx <= n && newy <= m) bombPos.push_back({newx, newy}); } } sort(bombPos.begin(), bombPos.end()); int cnt = unique(bombPos.begin(), bombPos.end()) - bombPos.begin();

memset(dp, 0x3f, sizeof dp);
dp[s] = 0;
int vis[11];
for (int i = s; i; i--) {
	memset(vis, 0, sizeof vis);
	bool flag = false; // 标记当前状态i是否合法
	for (int j = k, ii = i; j; j--) {
		if (ii & 3) vis[j] = 1; // 第j个位置有fish需要处理
		if ((ii & 3) > c[j]) { // 第j个位置的fish数量不对
			flag = true;
			break;
		}
		ii >>= 2;
	}
	if (flag) continue;
	// 依次遍历应该放炸弹的位置
	for (int j = 0; j < cnt; j++) {
		int x = bombPos[j].first, y = bombPos[j].second;
		int ii = i;
		for (int t = 0; t < 5; t++) {
			// fish编号
			int tmp = fish[x + dx[t]][y + dy[t]];
			if (vis[tmp]) ii -= (1 << ((k - tmp) << 1));
		}
		dp[ii] = min(dp[ii], dp[i] + 1);
	}
}

cout << dp[0];
return 0;

}