题目描述

LeavingZ 禁止 Blue-edged Shot 玩《原神》。不过，今天 LeavingZ 去华中科技大学网络空间安全学院参加了 2024 年湖北省大学生程序设计竞赛，准备夺取金牌。

《原神》中的“嘟嘟可砰砰历险记”活动开始了。这是一个单人游戏，每局游戏都有一个池塘。池塘可以划分为一个 $n$ 行 $m$ 列的网格，第 $i$ 行第 $j$ 列的格子记为 $(i,j)$。

其中有 $k$ 个格子里有鱼。你将扮演火花骑士可莉，使用炸弹捕鱼。

如果在 $(a,b)$ 处投放一枚炸弹，所有满足 $|x-a|+|y-b|\le1$ 的格子 $(x,y)$ 都会被爆炸覆盖。对于每个被覆盖且还有鱼的格子，这次爆炸都会捕到其中的 1 条鱼。

可莉可以在任意位置投放炸弹。请问，要捕到所有的鱼，最少需要投放多少枚“蹦蹦炸弹”？

输入格式

第一行三个整数 $n,m,k$，分别表示网格的行数、列数和有鱼的格子数量。

接下来 $k$ 行，每行三个整数 $x_i,y_i,a_i$，表示格子 $(x_i,y_i)$ 中有 $a_i$ 条鱼。

保证输入中的所有格子坐标 $(x_i,y_i)$ 互不相同。

输出格式

输出一个整数，表示所需的最少炸弹数量。

样例输入 1

5 5 3
1 1 2
2 2 1
5 5 2

样例输出 1

4

样例输入 2

1 1 1
1 1 3

样例输出 2

3

样例输入 3

1000 1000 2
1 1 1
1000 1000 3

样例输出 3

4

说明/提示

样例 1 的一种方案是在 $(1,2)$ 投放两枚炸弹，再在 $(5,5)$ 投放两枚炸弹，共 $4$ 枚。可以证明不存在使用更少炸弹的方案。

数据范围

满足 $1\le n,m\le10^3$，$1\le k\le10$。

满足 $1\le x_i\le n$，$1\le y_i\le m$，$1\le a_i\le3$。