Пасіанс#804

Пасіанс

1 секунда

256 мегабайтів

Легка

"N-T пасіанс" — карткова гра для одного гравця. У грі використовується $4 N$ карт, де кожна карта визначається унікальною парою значення (ціле число від $1$ до $N$ ) і масті ( $♠$ , $♡$ , $♢$ або $♣$ ).

На початку всі карти розкладені по $T$ купах ( $4 \leq T \leq 12$ 4 \leq T \leq 12). Перші $(4 N) mod T$ (4N) \bmod T куп містять по $(4 N // T) + 1$ (4N // T) + 1 карті, інші — по $4 N // T$ карт (тут $//$ — цілочисельне ділення, $mod$ — залишок від ділення).

Єдиний допустимий хід — взяти верхні карти будь-яких двох куп, якщо сума їх значень дорівнює $N + 1$ N+1 (незалежно від мастей), і покласти ці дві карти у відбій. Це єдиний спосіб видалити карти з гри.

Ваша задача — визначити максимальну кількість карт, яку можна перемістити у відбій.

Вхідні дані

Перший рядок містить два цілих числа $N$ і $T$ ( $3 \leq N \leq 15$ 3 \leq N \leq 15, $4 \leq T \leq 12$ 4 \leq T \leq 12).

Далі подано $T$ рядків, кожен з яких описує відповідну купу. Кожна карта задається своїм значенням (ціле число) і мастю (символ з ASCII-кодом $03$ ( $♠$ ), $04$ ( $♡$ ), $05$ ( $♢$ ) або $06$ ( $♣$ )) без пробілу між ними. Карти в межах однієї купи розділяються одним пробілом і перелічені знизу вгору.

Вихідні дані

Виведіть єдине ціле число — максимальну кількість карт, яку можна перемістити у відбій.

Приклади

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

Приклад 1