Вы играете в игру «Jongmah». В вашей руке есть \(n\) костей. На каждой кости написано целое число от \(1\) до \(m\).
Чтобы выиграть, вам нужно составить некоторое количество троек. Каждая тройка состоит из трёх костей, таких что или все числа на этих костях совпадают, или расположены последовательно. Например, \(7, 7, 7\) и \(12, 13, 14\) является корректными тройками, а \(2,2,3\) и \(2,4,6\) — нет. Каждую кость можно использовать не более чем в одной тройке.
Чтобы выяснить, насколько вы близки к победе, вы хотите узнать максимальное количество троек, которые вы можете составить.
Выходные данные
Выведите одно целое число — максимально возможное количество троек, которое вы можете составить.
Примечание
В первом примере у вас есть кости \(2, 3, 3, 3, 4, 4, 4, 5, 5, 6\). Мы можем составить три тройки следующим образом: \(2, 3, 4\); \(3, 4, 5\); \(4, 5, 6\). Так как всего есть только \(10\) костей, то составить \(4\) тройки точно не получится, а значит ответом является \(3\).
Во втором примере у вас есть кости \(1\), \(2\), \(3\) (\(7\) штук), \(4\), \(5\) (\(2\) штуки). Можно составить \(3\) тройки следующим образом: \(1, 2, 3\); \(3, 3, 3\); \(3, 4, 5\). Можно показать, что составить \(4\) тройки нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 6
2 3 3 3 4 4 4 5 5 6
|
3
|
|
2
|
12 6
1 5 3 3 3 4 3 5 3 2 3 3
|
3
|
|
3
|
13 5
1 1 5 1 2 3 3 2 4 2 3 4 5
|
4
|