Contest: Task: Related: TaskA TaskC

Score : $500$ points

AtCoDeer is thinking of painting an infinite two-dimensional grid in a *checked pattern of side $K$*.
Here, a checked pattern of side $K$ is a pattern where each square is painted black or white so that each connected component of each color is a $K$ $×$ $K$ square.
Below is an example of a checked pattern of side $3$:

AtCoDeer has $N$ desires.
The $i$-th desire is represented by $x_i$, $y_i$ and $c_i$.
If $c_i$ is `B`

, it means that he wants to paint the square $(x_i,y_i)$ black; if $c_i$ is `W`

, he wants to paint the square $(x_i,y_i)$ white.
At most how many desires can he satisfy at the same time?

- $1$ $≤$ $N$ $≤$ $10^5$
- $1$ $≤$ $K$ $≤$ $1000$
- $0$ $≤$ $x_i$ $≤$ $10^9$
- $0$ $≤$ $y_i$ $≤$ $10^9$
- If $i$ $≠$ $j$, then $(x_i,y_i)$ $≠$ $(x_j,y_j)$.
- $c_i$ is
`B`

or`W`

. - $N$, $K$, $x_i$ and $y_i$ are integers.

Input is given from Standard Input in the following format:

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

Print the maximum number of desires that can be satisfied at the same time.

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

4

He can satisfy all his desires by painting as shown in the example above.

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