«N-T пасьянс» — карткова гра для одного гравця. У грі використовується ~4N~ (~3\leqslant N\leqslant 15)~ карт, причому кожній карті відповідає унікальна пара її значення (ціле число в діапазоні ~1.\,.N~) та масті (~\spadesuit~, ~\clubsuit~, ~\heartsuit~ або ~\diamondsuit~). У початковому положенні всі карти розкладені у ~T~ (~4\leqslant T\leqslant 12)~ стопок; при цьому кожна з перших ~(4N)\%T~ стопок містить по ~(4N/T)+1~ карт, решта — по ~4N/T~ карт (тут / і % — цілочисельне ділення та остача від ділення відповідно). Якщо сума значень верхніх карт двох стопок дорівнює ~N+1~, то ці дві карти можна перемістити у відбій (незалежно від їхніх мастей). Це єдиний спосіб переміщувати карти.

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

Вхідні дані

Перший рядок містить два цілі числа ~N~ і ~T~, далі йдуть ~T~ рядків з описами карт відповідної стопки. Кожна карта описується її значенням (ціле число) та мастю (символ з ASCII-кодом 03(~\heartsuit~), 04(~\diamondsuit~), 05(~\spadesuit~) або 06(~\clubsuit~)) без пробілу між ними. Описи різних карт однієї стопки розділені рівно одним пробілом, напрямок опису зліва направо відповідає порядку карт знизу вгору.

Результати

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

Приклади

Вхід

3 5
2♠ 2♣ 2♥
2♦ 3♦ 1♥
3♣ 1♠
1♣ 3♥
1♦ 3♠

Результат

10

Примітки

Примітка 1

Задача зроблена на основі реальної гри Fourteen; наступна примітка містить скріншот саме з такої реалізації, у складі якоїсь старої версії ASP Linux.

Примітка 2

В задачі трохи неочевидне співвідношення, що вважається верхнім/нижнім/лівим/правим у грі, а що у вхідних даних.

Наприклад, позиція з картинки подавалась би приблизно так:

13 12
4♦ 12♣ 5♠ 7♠ 9♠
5♣ 11♦ 4♣ 4♠ 8♣
...
...
...

(Замість трикрапок ідуть іще 10 рядків, які описують подальші 10 стопок, дві з 5 картами і вісім з 4 картами.)

Примітка 3

В наведеному прикладі ~N=3~, тому знімати можна карти, сума яких рівна ~N+1=3+1=4~. Є кілька різних способів зробити чотири ходи, на кожному з яких знімається якась із трійок і якась із одиниць, і всі ці способи призводять до однакової ситуації (позиції), коли лишилося такі дві непорожні стопки:

2♠ 2♣ 2♥
2♦

Після цього, можна зняти ще 2♥ і 2♦ (бо саме вони верхні, і для них ~2+2=4~), після чого лишається єдина стопка

2♠ 2♣

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

Отже, з 12 карт вдається зняти 10.