꿀을 둘러싼 싸움

며칠 전 곰돌이 푸는 여느 때처럼 숲을 거닐다가 전에 한 번도 가 본 적 없는 곳에 이르렀다. 푸가 들어간 곳은 격자 모양의 공터였고, 칸마다 벌들이 사는 벌통이 하나씩 놓여 있었다. 푸는 몇 분 동안 말없이 서 있었다. 천국에 온 것 같았다. 그런데 뭔가 이상했다.

울타리. 담장. 울. 어쩌면 여러분은 푸가 왜 놀랐는지 이해하지 못할 수도 있다. 그래서 배경을 조금 설명하겠다. 벌은 아주 충성스러운 곤충이다. 벌이 누군가에게 정을 붙이면 그 사람만 오랫동안 섬긴다. 울타리로 둘러싸인 벌통은 벌에게 큰 영예다. 울타리는 벌을 지키고 싶다는 좋은 뜻을 보여 주기 때문이다. 울타리를 넘을 수 있는 자는 없고, 울타리가 없으면 누구든 벌에게 다가갈 수 있다. 벌은 이것을 잘 알고 있어서, 자기 주위에 울타리를 세운 쪽을 섬기기 시작한다.

다시 푸의 이야기로 돌아가자. 울타리를 본 푸는 곧바로 뭔가 잘못되었다고 의심했다. 울타리는 분명히 사람이 만든 것이었다. 숲 한가운데에 울타리가 저절로 생길 리는 없다. 푸는 경쟁자가 있다는 것을 깨달았고, 아무것도 하지 않으면 얼마나 많은 꿀을 잃을지 따져 본 뒤 행동하기로 했다.

푸는 숲에 숨어 이 지역의 벌을 차지하려는 낯선 자를 기다렸다. 밤새 기다린 끝에 아침에 운이 따랐다. 공터 맞은편에서 소리가 나더니 낯선 자가 널빤지를 끌고 오는 모습이 보였다. 자기 이익을 위해 쓸 셈이 분명했다. 낯선 자에게는 불운하게도, 푸도 준비를 잘해 두었다. 그 순간 푸는 이미 목표로 삼은 벌통을 향해 달리고 있었다. 그 벌통은 세 면이 이미 울타리로 막혀 있었다. 푸는 네 번째 울타리를 세워 그 벌통의 벌들을 자기 편으로 끌어들이고, 벌통을 자기 것으로 만들 생각이었다.

새로 편입된 벌들은 새 주인에게 충성을 보이려고 푸의 상대를 에워쌌다. 푸는 상대가 한 벌통의 벌에게 쫓겨 도망치는 동안 자기는 칸막이를 하나 더 세워 벌통을 또 하나 차지할 시간이 있다고 판단했다. 새로 차지한 벌통의 벌들도 상대를 공격한다. 게다가 서로 다른 벌통의 벌들은 사이가 그리 좋지 않다. 그래서 푸가 널빤지 하나를 놓아 벌통 두 개를 한꺼번에 차지하면, 상대를 공격하는 벌통은 하나뿐이다. 푸는 이런 식으로는 상대를 오래 붙잡아 둘 수 없다는 것을 알고, 그 전에 벌통을 몇 개나 차지할 수 있을지 알고 싶어 한다.

입력 파일에는 밭의 구성이 주어진다. 첫 줄에 밭의 크기 $n$과 $m$이 주어진다 ($1 \leq n, m \leq 1000$). 밭 바깥에는 벌통이 없다. 둘째 줄에는 이미 울타리가 있는 벌통의 개수 $t$가 주어진다.

이어지는 $t$개 줄에는 울타리가 있는 벌통에 대한 설명이 있다. 형식은 $x_i$ $y_i$ $c_i$ ... 이다 ($1 \leq x_i \leq n$, $1 \leq y_i \leq m$, $1 \leq c_i \leq 4$). $(x_i, y_i)$는 벌통의 좌표이고, $c_i$는 벌통 주변 울타리의 개수다. 그 뒤에 공백으로 구분된 서로 다른 문자 $c_i$개가 이어지며, 벌통이 어느 방향에서 둘러싸여 있는지 나타낸다. N은 북, S는 남, E는 동, W는 서다. $x$축은 동쪽을, $y$축은 북쪽을 가리킨다.

울타리 한 칸은 두 벌통에 인접해 있다. 예를 들어 벌통 $(x, y)$의 북쪽에 울타리가 있으면, 벌통 $(x+1, y)$의 남쪽에도 울타리가 있다.

입력 파일에서 울타리 한 칸은 한 번 또는 두 번 적힐 수 있다. 즉, 벌통 $(x, y)$의 북쪽에 울타리가 있다고 적혀 있다면, 벌통 $(x+1, y)$는 입력에 나타나지 않을 수도 있다.

푸가 사방을 모두 울타리로 둘러쌀 수 있는 벌통의 최대 개수를 정수 하나로 출력한다.