output_description: Print the maximum number of desires that can be satisfied at the same time.
  
  * * *
input_description: 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
attempt: def cumsum_2d(arr, cumsum_from="top_left"):
      K = len(arr)  # arr: K * K array
      ret = [[0 for _ in range(K)] for _ in range(K)]
      # 行方向に累積和
      for y in range(K):
          v = 0
          for x in range(K):
              if "right" in cumsum_from:
                  x = K - 1 - x
              v += arr[y][x]
              ret[y][x] = v
      # 列方向に累積和
      for y in range(1, K):
          before_y = y - 1
          if "bottom" in cumsum_from:
              y = K - 1 - y
              before_y = y + 1
          for x in range(K):
              ret[y][x] += ret[before_y][x]
      return ret
  
  
  def main():
      N, K = list(map(int, input().split()))
      # 同じ色になるセルをひとまとめにする
      field_even = [[0 for _ in range(K)] for _ in range(K)]
      field_odd = [[0 for _ in range(K)] for _ in range(K)]
      for _ in range(N):
          X, Y, C = input().split()
          X = int(X) - 1
          Y = int(Y) - 1
          white_flag = 1 if C == "W" else 0
          score = X // K + Y // K + white_flag
          if score % 2 == 0:
              field_even[Y % K][X % K] += 1
          else:
              field_odd[Y % K][X % K] += 1
      # 右上・右下・左上・左下からの2次元累積和
      even_tr = cumsum_2d(field_even, "top_right")
      even_br = cumsum_2d(field_even, "bottom_right")
      even_tl = cumsum_2d(field_even, "top_left")
      even_bl = cumsum_2d(field_even, "bottom_left")
      odd_tr = cumsum_2d(field_odd, "top_right")
      odd_br = cumsum_2d(field_odd, "bottom_right")
      odd_tl = cumsum_2d(field_odd, "top_left")
      odd_bl = cumsum_2d(field_odd, "bottom_left")
      # K * Kの正方形内の分割方法を全通り試して答えを求める
      # 分割のうち、左上の正方形の右下のセルの座標で場合分け
      ans = 0
      for y in range(-1, K):
          for x in range(-1, K):
              # pattern 1
              c = 0
              if y >= 0 and x >= 0:
                  c += even_tl[y][x]
              if y + 1 < K and x + 1 < K:
                  c += even_br[y + 1][x + 1]
              if y + 1 < K and x >= 0:
                  c += odd_bl[y + 1][x]
              if y >= 0 and x + 1 < K:
                  c += odd_tr[y][x + 1]
              ans = max(ans, c)
              # pattern 2(oddとeven入れ替え（白黒反転）)
              c = 0
              if y >= 0 and x >= 0:
                  c += odd_tl[y][x]
              if y + 1 < K and x + 1 < K:
                  c += odd_br[y + 1][x + 1]
              if y + 1 < K and x >= 0:
                  c += even_bl[y + 1][x]
              if y >= 0 and x + 1 < K:
                  c += even_tr[y][x + 1]
              ans = max(ans, c)
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: 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:
  
  ![cba927b2484fad94fb5ff7473e9aadef.png](https://img.atcoder.jp/arc089/cba927b2484fad94fb5ff7473e9aadef.png)
  
  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?
samples: [{"input": "4 3\n    0 1 W\n    1 2 W\n    5 3 B\n    5 4 B", "output": "4\n    \n\nHe can satisfy all his desires by painting as shown in the example above.\n\n* * *"}, {"input": "2 1000\n    0 0 B\n    0 1 W", "output": "2\n    \n\n* * *"}, {"input": "6 2\n    1 2 B\n    2 1 W\n    2 2 B\n    1 0 B\n    0 6 W\n    4 5 W", "output": "4"}]