Битва за мёд
Несколько дней Винни Пух как ни в чём не бывало прогуливался по лесу, и попал в место, где раньше ни разу не был. Пух попал на клетчатую поляну, в каждой клетке которой находился улей с пчёлами. На несколько минут Винни замер и потерял дар речи. Ему казалось, что он попал в рай. Но что-то здесь было не так...
Заборы. Загородки. Ограды. Возможно, вы не понимаете удивления Пуха. Чтобы пояснить его, дадим небольшую справку. Пчёлы, как известно, - очень преданные насекомые. Если они привязались к кому-то, то они будут очень долго служить только ему. Улей же, окружённый забором, является большой честью для пчёл. Так можно показать пчёлам свои добрые намерения, желание защищать их. Ведь никто не полезет через забор, а при отсутствии оного, к пчёлам может придти кто угодно. Пчёлы это прекрасно понимают, и начинают служить тому, кто этот забор вокруг них возвёл.
Вернёмся же теперь к Винни. Заметив заборы, он сразу заподозрил что-то неладное. Они были явно искусственного происхождения. Действительно, откуда ещё могут взяться заборы посреди леса? Поняв, что у него есть конкурент и оценив, сколько мёда он потеряет, если ничего не предпримет, он решился действовать.
Пух затаился в лесу и стал ждать того незнакомца, который захотел заполучить себе местных пчёл. Всю ночь он провёл в его ожидании, но утром удача ему улыбнулась. Он услышал какой-то шум с противоположной стороны поляны и увидел незнакомца, который тащил доски с явным намерением использовать их в своих корыстных целях. К его несчатью, Винни тоже хорошо подготовился. А именно, в этот момент он уже бежал к выбранному улью, уже огороженному с трёх сторон, чтобы поставить четвёртое ограждение, тем самым переманив пчёл этого улья на свою сторону и захватив улей себе в подчинение.
Новообращенные пчёлы решили проявить преданность своему новому господину и окружили противника Пуха. Винни оценил, что пока его визави бегает от пчел из одного улья, у него самого есть время поставить еще одну перегородку и, возможно, захватить еще один улей. Пчелы из новозахваченного улья также нападают на противника Винни. К тому же так как отношения между пчелами из разных ульев не слишком дружелюбны, то если Пух, поставив одну доску, захватывает сразу два улья, то на его противника нападает только один улей. Пух понимает, что долго таким образом задерживать своего противника не сможет, и хочет узнать, сколько ульев он успеет захватить.
Входные данные
Во входном файле задана конфигурация поля. В первой строке заданы числа n и m (1 ≤ n, m ≤ 1000) - размеры поля. Вне поля ульев нет. Во второй строке задано число ульев t, рядом с которыми уже стоят заборы.
Далее в t строках идёт само их описание. Оно имеет вид x_i y_i c_i ... (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, 1 ≤ c_i ≤ 4) - координаты улья, рядом с которым что-то есть, количество оград вокруг него, а затем, вместо ... через пробел идут c_i различных букв N, S, E, W - с каких сторон улей окружён. N - север, S - юг, E - восток, W - запад. Ось x направлена на восток, y - на север.
Каждая перегородка является соседней для двух ульев. Если, например, у улья (x, y) на северной его части есть забор, то у улья с координатами (x + 1, y) будет забор в южной части.
Во входном файле каждый кусок забора может быть указан один или два раза. То есть, если сказано, что у улья (x, y) на севере есть забор, то улей (x + 1, y) может быть не указан во входном файле.
Выходные данные
Выведите единственное целое число - максимальное количество ульев, которые Винни успеет окружить забором со всех сторон.