P10865 [HBCPC2024] Genshin Impact Startup Forbidden III

“Blue-edged Shot 被 LeavingZ 禁止玩《原神》。然而，今天 LeavingZ 前往了华中科技大学的网络科学与工程学院，参加2024年中国湖北省国际大学生程序设计竞赛，并收获了金牌。 《原神》中的一个活动多多炸弹大冒险已经开始了。这是一个单人游戏，每局游戏都涉及一个池塘。池塘可以被划分为一个 $n×m$ 的网格，其中第 $i$ 行第 $j$ 列的单元格表示为 $(i,j)$。在这些单元格中，有 $k$ 个单元格包含鱼，你将扮演火花骑士克莱，她用炸药来捕鱼。 如果克莱在 $(a,b)$ 位置投放炸弹，那么所有满足$|x-a|+|y-b|\le 1$的单元格 $(x,y)$ 都将被爆炸覆盖。对于每一个被爆炸覆盖的单元格，克莱都会从其中捕到一条鱼。克莱可以在任何位置投放炸弹。问题是，为了捕到所有的鱼，至少需要多少枚“蹦蹦炸弹”？

第一行包含三个整数 $n,m,k$ ($1 \le n,m \le 10^3, 1 \le k \le 10$)，分别表示网格的大小（行数和列数）以及包含鱼的单元格数量。 接下来的 $k$ 行，每行包含三个整数 $x_i,y_i,a_i$ ($1\le x_i \le n, 1 \le y_i \le m, 1 \le a_i \le 3$)，表示在网格的 ($x_i, y_i$) 单元格中有 $a_i$ 条鱼。 输入保证所有的 $(x_i, y_i)$ 单元格坐标都是唯一的。

输出一个整数，表示所需的最少炸弹数量。” 在这个问题中，你需要计算并输出一个整数，该整数代表为了捕获所有鱼所需投放的最少“蹦蹦炸弹”数量。

一种可能的方法是在 $(1,2)$ 位置投放两枚炸弹，再在 $(5,5)$ 位置投放另外两枚炸弹。 可以证明没有比这个答案更小的解。