Battle for Honey

A few days ago Winnie the Pooh was strolling through the forest as if nothing had happened, and he wandered into a place he had never visited before. He came to a grid-shaped clearing where every cell held a beehive. For several minutes Winnie stood frozen and speechless. It seemed to him he had reached paradise. But something was off.

Fences. Pens. Enclosures. You may not understand Pooh's surprise, so here is some background. Bees are known to be very devoted insects. Once they attach themselves to someone, they serve that one alone for a long time. A hive surrounded by a fence is a great honor for bees. It shows them your good intentions and your wish to protect them. Nobody can climb over a fence, while without one, anyone can approach the bees. The bees understand this well and start serving whoever built the fence around them.

Now back to Winnie. Seeing the fences, he immediately suspected something was wrong. They were clearly man-made. Where else could fences in the middle of a forest come from? Realizing he had a competitor and estimating how much honey he would lose if he did nothing, he decided to act.

Pooh hid in the forest and waited for the stranger who wanted the local bees. He waited all night, and in the morning luck smiled on him. He heard noise from the far side of the clearing and saw the stranger dragging boards, clearly planning to use them for selfish ends. Unfortunately for the stranger, Winnie had also prepared well. At that moment he was already running toward a chosen hive that was fenced on three sides. He meant to build a fourth fence, win over that hive's bees, and take the hive under his control.

The newly converted bees wanted to show their loyalty to their new master, and they surrounded Pooh's opponent. Winnie figured that while his rival was running from the bees of one hive, he would have time to build another partition and possibly take another hive. The bees of the newly captured hive also attack Winnie's opponent. Also, bees from different hives are not very friendly with each other, so when Pooh places one board and captures two hives at once, only one hive attacks his opponent. Pooh knows he cannot keep his opponent busy this way for long, and he wants to know how many hives he can capture before then.

The input file describes the field. The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 1000$), the size of the field. There are no hives outside the field. The second line contains the number $t$ of hives that already have fences around them.

Each of the next $t$ lines has the form $x_i$ $y_i$ $c_i$ ... ($1 \leq x_i \leq n$, $1 \leq y_i \leq m$, $1 \leq c_i \leq 4$). Here $(x_i, y_i)$ are the coordinates of the hive, $c_i$ is the number of fences around it, and then come $c_i$ distinct letters N, S, E, W separated by spaces, indicating the sides where the hive is enclosed. N is north, S is south, E is east, and W is west. The x axis points east and the y axis points north.

Each fence segment is adjacent to two hives. For example, if hive $(x, y)$ has a fence on its north side, then hive $(x+1, y)$ has a fence on its south side.

In the input file, each fence segment may be listed once or twice. That is, if the input says hive $(x, y)$ has a fence on its north side, hive $(x+1, y)$ may not be listed.

Print a single integer: the maximum number of hives that Winnie can fully surround with fences on all four sides.