分数: 500 点
问题陈述
AtCoDeer 正在考虑在一个无限二维网格中绘制一个 侧面格子图案 K。 这是侧面的格子图案 K 是一种模式,其中每个正方形都被漆成黑色或白色,以便每种颜色的每个连通分量都是一个 K × K 广场。 下面是侧面格子图案的示例 3:
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
BorW. - 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