Battle for Honey#2369
A few days ago, Winnie the Pooh was wandering through the forest when he stumbled upon a place he had never seen before. 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 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 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 and serve whoever builds the fence around them.
Now, back to Winnie. Upon noticing the fences, he immediately sensed that something was wrong. They were clearly man-made. Where else would fences come from in the middle of the forest? 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 to claim the local bees. 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, intending to use them for his own purposes. But Winnie was ready. He quickly ran to a hive 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 surrounded Pooh's opponent. Winnie realized that while his adversary was running from one hive's bees, he had time to place another fence and perhaps capture another hive. The bees from the new hive also attacked Winnie's opponent. Furthermore, since bees from different hives are not friendly towards each other, if Pooh, by placing one board, surrounds two hives at the same time, only one hive will attack his opponent. Pooh knows he can't delay his opponent like this for long and wants to find out how many hives he can fully surround with fences.
The clearing looks like a rectangle of size n \times m. The field contains several hives, some of which already have fences next to them. Fences are adjacent to the sides of the cells. Each side of a cell may either be fenced or not.
The input file describes the field configuration. The first line contains the numbers and (1 \leq n, m \leq 1000) — the dimensions of the field. There are no hives outside the field. The second line specifies the number of hives that already have fences next to them.
Then, lines follow, each describing a hive. The format is x_i y_i c_i ... (1 \leq x_i \leq n, 1 \leq y_i \leq m, 1 \leq c_i \leq 4) — the coordinates of the hive, the number of fences around it, and then, separated by spaces, c_i different letters , , , indicating which sides of the hive are fenced. — north, — south, — east, — west. The axis points east, and the axis points north.
Each fence is adjacent to two hives. For example, if a hive 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 part may be specified once or twice. That is, if it is stated that hive has a fence to the north, then hive (x + 1, y) may not be mentioned in the input file.
Print a single integer — the maximum number of hives that Winnie can fully surround with fences.
Example 1