题目描述

シカ的 AtCoDeer 君想要用边长为 $K$ 的“市松模様”来涂满一张无限大的二维网格。其中，边长为 $K$ 的“市松模様”是指将网格以白色和黑色交替着色，且每种颜色的每个连通块恰好是 $K \times K$ 的正方形。例如，下面就是边长为 $3$ 的“市松模様”的一个例子。

AtCoDeer 君有 $N$ 个愿望。第 $i$ 个愿望用 $x_i, y_i, c_i$ 表示。如果 $c_i$ 是 B，表示希望 $(x_i, y_i)$ 这个格子被涂成黑色；如果 $c_i$ 是 W，表示希望它被涂成白色。请你计算，最多能同时满足多少个愿望。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

输出能同时满足的愿望数量的最大值。

样例 1

输入

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

输出

4

样例 2

输入

2 1000
0 0 B
0 1 W

输出

2

样例 3

输入

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

输出

4

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 1000$
• $0 \leq x_i \leq 10^9$
• $0 \leq y_i \leq 10^9$
• 如果 $i \neq j$，则 $(x_i, y_i) \neq (x_j, y_j)$
• $c_i$ 为 B 或 W
• $N, K, x_i, y_i$ 都是整数

样例解释 1

像上面给出的例子那样去涂色，可以同时满足所有的愿望。

由 ChatGPT 5 翻译