题目描述

シカのAtCoDeerくんは無限に広がる二次元グリッドを一辺が $K$ の市松模様で塗ろうと考えています。 ただし、一辺が $K$ の市松模様とは、各マスが白か黒で塗られたパターンであって、各色の各連結成分が $K$ $×$ $K$ の正方形となっているようなものです。 例えば以下は一辺が $3$ の市松模様の例です。

AtCoDeerくんは $N$ 個の希望を持っています。 $i$ 個目の希望は、 $x_i,y_i,c_i$ で表されます。 これは、$c_i$ が B ならマス $(x_i,y_i)$ を黒で塗る、 W なら白で塗ることを意味しています。 同時に最大でいくつの希望を叶えることが出来るか答えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

同時に叶えられる希望の個数の最大値を出力せよ。

题目大意

有一个无限大的黑白网格，由若干个 $K\times K$ 的黑色或白色正方形矩阵构成，且相间分布。

给定 $N$ 个愿望，每个愿望给定 $x_i,y_i,c_i$，表示想要使 $(x_i,y_i)$ 的网格是 $c_i$ 种颜色，问最多可以同时满足多少个愿望。

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

4

2 1000
0 0 B
0 1 W

2

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

4

提示

制約

• $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$ は整数

Sample Explanation 1

上であげた例のように塗ればすべての希望を同時に叶えることができます。