Vasya and Petya are playing the following game. They take a deck of 36 cards. Each card has a number from 1 to 9 written on it and each card is painted in one of 4 colors so that there are exactly 9 cards of each color, and they are numbered from 1 to 9. The cards are shuffled and players are dealt several (no more than 18) cards.
Then the players take turns making moves. In one move, a player can put one or several cards consecutively on the table according to the following rules. A card with the number 5 of any color can be laid out on the table without additional conditions. A card with a different number can be laid out only if a card of the same color has already been laid out on the table, on which a number is written 1 more or 1 less than this one, or a card with the same number, but of a different color (it does not matter whether it was this card was placed by you or your opponent, and whether it was placed on or before the previous turn). If a player cannot lay out a single card, he skips a turn.
Write a program that, based on information about which cards are already on the table and which ones the player has, will determine the maximum number of cards that this player can lay out on a given move.
Input
The input file contains first the number K — the number of cards already laid out on the table. Next comes K pairs of numbers describing these cards. Then the number N — the number of cards in the hand of the player who must now make a move. Next, there are N pairs of numbers describing these cards.
Each card is described by two numbers — color number (from 1 to 4) and the number that is written on the card (from 1 to 9).
Limits: 0≤K≤35, 1≤N≤36, N+K≤36, all cards are different.
Imprint
In the output file print a single number — the maximum number of cards that can be played on a given turn.
Examples
| # |
Input |
Output |
Comments |
| 1 |
2
15
14
3
1 3
16
28 |
2 |
These are cards 1 3 (because there are 1 4 on the table) and 1 6 (because there are 1 5 on the table) |
| 2 |
0
4
28
15
36
16 |
3 |
In the first move, we can play 1 5, after that we have the right to play 1 6, after which we play 3 6 |
| 3 |
3
14
15
16
2
28
29 |
0 |
Can't post any cards |