#AT1180. D - Checker
D - Checker
当前没有测试数据。
D - Checker
Score : $500$ points
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
orW
. - $N$, $K$, $x_i$ and $y_i$ are integers.
Input
Input is given from Standard Input in the following format:
Output
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