← 返回题目列表

AtCoder · arc089_b

D. 检查器

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

AtCoDeer 正在考虑在一个无限二维网格中绘制一个 侧面格子图案 K。 这是侧面的格子图案 K 是一种模式,其中每个正方形都被漆成黑色或白色,以便每种颜色的每个连通分量都是一个 K × K 广场。 下面是侧面格子图案的示例 3:

cba927b2484fad94fb5ff7473e9aadef.png

AtCoDeer 有 N 的愿望。 的 i-th 愿望表示为 x_i, y_i 和 c_i。 如果 c_i is B,这意味着他要绘制正方形 (x_i,y_i) 黑色;如果 c_i is W,他想画正方形 (x_i,y_i) 白色。 他最多可以同时满足多少个欲望?

约束

  • 1 ≤ N ≤ 10^5
  • 1 ≤ K ≤ 1000
  • 0 ≤ x_i ≤ 10^9
  • 0 ≤ y_i ≤ 10^9
  • If i ≠ j,那么 (x_i,y_i) ≠ (x_j,y_j).
  • c_i is B or 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