Solitaire#804

Solitaire

1 second

256 megabytes

Easy

"N-T Solitaire" is a single-player card game played with $4 N$ cards, where each card is uniquely defined by a pair consisting of its value (an integer in the range $1$ to $N$ ) and its suit ( $♠$ , $♡$ , $♢$ , or $♣$ ).

The game begins with all cards dealt among $T$ piles ( $4 \leq T \leq 12$ 4 \leq T \leq 12). The cards are distributed so that the first $(4 N) mod T$ (4N) \bmod T piles contain $(4 N // T) + 1$ (4N // T) + 1 cards each, and the remaining piles contain $4 N // T$ cards each (here, $//$ denotes integer division and $mod$ denotes the remainder).

The only valid move in the game is to choose the top cards of any two piles whose values sum to $N + 1$ N+1 (regardless of suits), and move both cards to the discard pile. This is the only way to remove cards from play.

Your task is to determine the maximum number of cards that can be moved to the discard pile.

Input

The first line contains two integers $N$ and $T$ ( $3 \leq N \leq 15$ 3 \leq N \leq 15, $4 \leq T \leq 12$ 4 \leq T \leq 12).

Then follow $T$ lines, each describing one pile. Each card is described by its value (an integer) followed directly by its suit (a character with ASCII code $03$ ( $♠$ ), $04$ ( $♡$ ), $05$ ( $♢$ ), or $06$ ( $♣$ )), with no space between them. Cards in each pile are separated by a single space and are listed from bottom to top.

Output

Output a single integer: the maximum number of cards that can be moved to the discard pile.

Examples

5 4
1\spadesuit 2\spadesuit 3\spadesuit 4\spadesuit 5\spadesuit
1\heartsuit 2\heartsuit 3\heartsuit 4\heartsuit 5\heartsuit
1\diamondsuit 2\diamondsuit 3\diamondsuit 4\diamondsuit 5\diamondsuit
1\clubsuit 2\clubsuit 3\clubsuit 4\clubsuit 5\clubsuit

Example 1