Battle for Honey
A few days ago, Winnie the Pooh was wandering through the forest when he stumbled upon a new area. It was a checkered clearing, and each cell contained a beehive. For a moment, Pooh was speechless. It seemed he had discovered paradise. But something was off...
Fences. Small fences. Barriers. You might not understand Pooh's surprise, so let's provide some context. Bees are known for their loyalty. Once they bond with someone, they serve them faithfully for a long time. A beehive surrounded by a fence is a great honor for bees. It shows them your good intentions and desire to protect them. After all, no one will climb over a fence, but without it, anyone could approach the bees. Bees understand this perfectly and begin to serve the one who erected the fence around them.
Now, back to Winnie. Upon noticing the fences, he immediately sensed something was wrong. They were clearly man-made. After all, where else would fences come from in the middle of the forest? Realizing he had a competitor and calculating 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 to claim the local bees for himself. He waited all night, and in the morning, his patience paid off. He heard a noise from the opposite side of the clearing and saw a stranger carrying boards, clearly intending to use them for his own gain. Unfortunately for the stranger, Winnie was ready. He quickly ran to a hive that was already fenced on three sides and placed the fourth fence, thus winning over the bees of that hive and taking control of it.
The newly loyal bees decided to show their allegiance to their new master by surrounding Pooh's opponent. Winnie realized that while his adversary was fleeing from the bees of one hive, he had time to place another fence and possibly capture another hive. The bees from the newly captured hive also attacked Winnie's opponent. Moreover, since bees from different hives don't get along well, if Pooh captures two hives at once by placing one board, only one hive will attack his opponent. Pooh knows he can't hold off his opponent for long this way and wants to find out how many hives he can fully surround with fences.
Input
The input file describes the field configuration. The first line contains the numbers n and m (1 ≤ n, m ≤ 1000) - the dimensions of the field. There are no hives outside the field. The second line specifies the number of hives t, next to which fences are already standing.
Then, t lines follow, each describing a hive. The format is x_i y_i c_i ... (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, 1 ≤ c_i ≤ 4) - the coordinates of the hive, the number of fences around it, followed by c_i different letters N, S, E, W - indicating which sides the hive is fenced. N - north, S - south, E - east, W - west. The x axis points east, and the y axis points north.
Each fence is shared by two hives. For instance, if a hive (x, y) has a fence on its northern side, then the hive at (x + 1, y) will have a fence on its southern side.
In the input file, each fence can be mentioned once or twice. That is, if it states that a hive (x, y) has a fence to the north, the hive (x + 1, y) might not be mentioned in the input file.
Output
Output a single integer - the maximum number of hives Winnie can completely surround with fences.