Задача Newnumbers. Козак Вус подарував вам набiр з n цифр (тобто чисел вiд 0 до 9 включно). I хоче дiзнатися у вас: яку максимальну кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які цифри з набору, вибрати їхнiй порядок та скласти число з цих цифр. Звернiть увагу, що ви не зобов’язанi використати всi цифри. Ви ж не можете вiдмовити Вусу? :)
Маленька пiдказка вiд Математичної Сови:
-
Остача (залишок) вiд дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр числа x на число 3.
-
Число a є кратним числу b (тобто a дiлиться на b) лише, якщо остача вiд дiлення числа a на число b дорiвнює 0.
Технічні умови Програма Newnumbers читає з пристрою стандартного введення у першому рядку мiстить одне цiле число n (1 ⩽ n⩽5 · 105) — кiлькiсть цифр. У другому рядку записано n цiлих чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного виведення одне ціле число — максимальну кількість чисел кратних 3, що можна скласти з цього набору.
Приклади
| Введення | Виведення |
| 1 0 |
1 |
| 14 8 8 4 8 1 1 0 0 2 1 9 3 4 1 |
8 |
Зауваження до прикладів
У першому прикладі ми можемо скласти лише одне число 0.
У другому прикладі з цього набору ми можемо скласти максимум 8 чисел. Один iз можливих способів — це скласти такі числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться цифри 1, 1.