Задача: Выложите побольше карт
Вася и Петя играют в следующую игру. Они берут колоду из 36 карточек. На каждой карточке написано число от 1 до 9 и каждая карточка покрашена в один из 4 цветов так, что есть ровно по 9 карточек каждого цвета, и они пронумерованы числами от 1 до 9. Карты перемешиваются, и игрокам раздается по несколько (не более чем по 18) карточек.
Дальше игроки по очереди делают ходы. За один ход игрок может выложить на стол одну или последовательно несколько карточек по следующим правилам. Карточку с цифрой 5 любого цвета можно выкладывать на стол без дополнительных условий. Карточку с другой цифрой можно выкладывать только если на стол уже выложена карточка того же цвета, на которой написано число на 1 большее или на 1 меньшее, чем на данной, или же карточка с той же цифрой, но другого цвета (не важно, была ли эта карточка выложена вами или вашим противником, и была ли она выложена на предыдущем ходе или раньше). Если ни одну карточку игрок выложить не может, он пропускает ход.
Напишите программу, которая по информации о том, какие карточки уже лежат на столе и какие есть у игрока, определит наибольшее число карточек, которое может быть выложено этим игроком на данном ходе.
Входные данные
Во входном файле записано сначала число K — количество уже выложенных на стол карточек. Далее идет K пар чисел, описывающих эти карточки. Затем записано число N — количество карточек на руках у игрока, который сейчас должен делать ход. Далее записано N пар чисел, описывающих эти карточки.
Каждая карточка описывается двумя числами — номером цвета (от 1 до 4) и цифрой, которая написана на карточке (от 1 до 9).
Ограничения: 0≤K≤35, 1≤N≤36, N+K≤36, все карточки различны.
Выходные данные
В выходной файл выведите одно число — наибольшее количество карточек, которые могут быть выложены на данном ходе.
Примеры
| № |
Входные данные |
Выходные данные |
Комментарии |
| 1 |
2
1 5
1 4
3
1 3
1 6
2 8 |
2 |
Это карты 1 3 (потому что на столе есть 1 4) и 1 6 (потому что на столе есть 1 5) |
| 2 |
0
4
2 8
1 5
3 6
1 6 |
3 |
Первым ходом можно выложить 1 5, после этого мы имеем право выложить и 1 6, после которой выкладываем 3 6 |
| 3 |
3
1 4
1 5
1 6
2
2 8
2 9 |
0 |
Нельзя выложить ни одной карточки |
Ваш ответ: