Битва за мед#2369
Кілька днів тому Вінні-Пух блукав лісом, коли натрапив на місце, де ще ніколи не був. Це була шахова галявина, і в кожній клітинці знаходився вулик. На мить Пух онімів. Здавалося, він відкрив рай. Але щось було не так...
Парканчики. Маленькі огорожі. Ви, можливо, не зрозумієте здивування Пуха, тож ось трохи контексту. Бджоли відомі своєю вірністю. Як тільки вони прив'язуються до когось, то служать йому довго і віддано. Вулик, обнесений парканом — велика честь для бджіл. Це демонстрація ваших добрих намірів і бажання їх захистити. Адже ніхто не перелізе паркан, а без нього до бджіл зможе наблизитися кожен. Бджоли це розуміють і вірно служать тому, хто їм збудував паркан.
Повернемося до Вінні. Помітивши паркани, він одразу усвідомив: щось тут не так. Очевидно, що ці огорожі поставила людина. Звідки ж іще посеред лісу взятися парканам? Зрозумівши, що має конкурента та прикинувши, скільки меду втратить, якщо нічого не вдіє, Пух вирішив діяти.
Пух заховався в лісі й став чекати на незнайомця, який намагався привласнити місцевих бджіл. Він чекав усю ніч, а зранку його терпіння було винагороджено. З протилежного краю галявини долинув шум — з’явився незнайомець із дошками, який мав намір використати їх у своїх цілях. Але Вінні був напоготові. Він хутко підбіг до вулика, вже обгородженого з трьох боків, і встановив четвертий парканчик, вигравши ласку бджіл цього вулика та підкоривши його собі.
Нові вірні бджоли обступили супротивника Пуха. Вінні зрозумів, що доки його противник утікає від бджіл одного вулика, він встигає встановити ще один паркан, а отже, захопити ще один вулик. Бджоли з нового вулика також переслідували противника Пуха. Більше того, оскільки бджоли з різних вуликів недружні між собою, якщо Пух, встановивши одну дошку, обнесе відразу два вулики, нападати на супротивника буде лише один вулик. Вінні знає, що не зможе так затримувати супротивника довго й хоче дізнатися, скільки вуликів він зможе повністю обнести парканом.
Галявина має прямокутну форму розміру n \times m. На полі розташовано декілька вуликів, деякі з них уже мають паркани поруч із собою. Паркан прилягає до бокової сторони клітинки. Кожна сторона клітинки може мати або не мати паркан.
Вхідний файл описує конфігурацію поля. У першому рядку задані числа та (1 \leq n, m \leq 1000) — розміри поля. Поза межами поля вуликів немає. Другий рядок містить кількість вуликів , які вже мають паркани поруч.
Далі йде рядків, кожен описує один вулик. Формат: x_i y_i c_i ... (1 \leq x_i \leq n, 1 \leq y_i \leq m, 1 \leq c_i \leq 4) — координати вулика, кількість парканів біля нього, а потім, через пробіл, c_i різних літер , , , , що вказують, з яких сторін вулик обнесено парканом. — північ, — південь, — схід, — захід. Вісь спрямована на схід, вісь — на північ.
Кожен паркан прилягає до двох вуликів. Наприклад, якщо у вулика встановлено паркан з північного боку, то у вулика (x + 1, y) буде паркан із південного боку.
У вхідному файлі кожен паркан може бути вказаний один або два рази. Тобто, якщо для вулика зазначено наявність паркану з півночі, то для вулика (x + 1, y) це може бути і не згадано.
Виведіть єдине ціле число — максимальну кількість вуликів, які Вінні зможе повністю обнести парканом.
Приклад 1