题目描述

在《传送门》这款游戏中，玩家会获得一把传送枪，在任意位置可以打出传送门，当打出两个传送门时，这两个传送门将会连通，以此来完成一些任务或者穿越一些障碍。

现在这个游戏出了一个定点传送模式。

在这个模式下，玩家将会进入到一个 $n * m$ 的迷宫中，这个迷宫共有 $n * m$ 个房间，并且房间之间完全堵死，无法通行。

在这些迷宫中，将会存在 $k$ 个地点拥有传送门，并且在这个模式下，将会有三种特殊的传送门用编号 $A,B,C$ 表示：

• 若 $(x,y)$ 这个房间的是 $A$ 类传送门，则可以传送到周围一圈的房间，即 $(上，下，左，右，左上，右上，左下，右下)$
• 若 $(x,y)$ 这个房间的是 $B$ 类传送门，则可以传送到 $(x,i)$ 房间，其中 $1 \leq i \leq m$
• 若 $(x,y)$ 这个房间的是 $C$ 类传送门，则可以传送到 $(i,y)$ 房间，其中 $1 \leq i \leq n$

注意：所有的传送门均是单向传送

现在作为玩家，你可以任选一个房间作为起点，并从这个起点出发选择一条路线（不能多次从起点出发走不同路线）使用传送门到达其他地点，记过程中使用的传送门数量为S。你的任务是尽量最大化可以使用传送门的数量S。

注意：一个传送门可以重复使用，一个房间可以重复到达，但是重复使用同一个传送门只计算一次答案。

输入格式

输入第一行包含三个整数 $n,m,k$ 表示地图大小及传送门数量

接下来 $k$ 行，每行用形如 $x_i,y_i,z_i$ 的形式表示一个传送门在 $(x_i,y_i)$ 处，种类为 $z_i \in [A,B,C]$。

输出格式

输出一个数字表示最多能使用的传送门数量。

7 7 10
2 2 B
2 4 C
1 7 C
2 7 A
4 2 C
4 4 B
6 7 A
7 7 B
7 5 C
5 2 B

9

数据规模与约定

每组数据点10分，共10组数据。

对于所有的数据，保证同一个地点不会有多个传送门。

大样例

大样例下载