配点 : $500$ 点

問題文

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

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

制約

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

入力

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

$N$ $K$

$x_1$ $y_1$ $c_1$

$x_2$ $y_2$ $c_2$

$:$

$x_N$ $y_N$ $c_N$

出力

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

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