100863: [AtCoder]ABC086 D - Checker

Problem Statement

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?

Constraints

• $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

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$

Output

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

Sample Input 1

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

Sample Output 1

4

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

Sample Input 2

2 1000
0 0 B
0 1 W

Sample Output 2

2

Sample Input 3

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

Sample Output 3

4