问题描述

AtCoDeer 打算在一个无限的二维网格上绘制一个 "边长为 K 的方格格子图案"。这里，边长为 K 的方格格子图案是指每个方格都被涂成黑色或白色，以使得每种颜色的每个连通分量都是一个 K × K 的正方形。下面是一个边长为 3 的方格格子图案的示例：

AtCoDeer 有 N 个需求。第 i 个需求由 xi、yi 和 ci 表示。如果 ci 是 B，则表示他希望将方格(xi,yi)涂成黑色；如果 ci 是 W，则表示他希望将方格(xi,yi)涂成白色。他最多能同时满足多少个需求？

约束条件

• $1$ $≤$ $N$ $≤$ $10^5$
• $1$ $≤$ $K$ $≤$ $1000$
• $0$ $≤$ $x_i$ $≤$ $10^9$
• $0$ $≤$ $y_i$ $≤$ $10^9$
• 如果 $i$ $≠$ $j$，那么 $(x_i,y_i)$ $≠$ $(x_j,y_j)$。
• $c_i$ 是 B 或 W。
• $N$、$K$、$x_i$ 和 $y_i$ 都是整数。

输入

输入数据从标准输入读取。数据格式如下：

$N$ $K$ $x_1$ $y_1$ $c_1$ $x_2$ $y_2$ $c_2$ $:$ $x_N$ $y_N$ $c_N$

输出

打印能够同时满足的最大需求数。

示例输入1

4 3
0 1 W
1 2 W
5 3 B
5 4 B

示例输出1

4

他可以按照上面的例子中所示的方式满足所有的需求。

示例输入2

2 1000
0 0 B
0 1 W

示例输出2

2

示例输入3

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

示例输出3

4