Задача Newnumbers. Козак Вус подарував вам набiр з цифр (тобто чисел вiд 0 до 9 включно). I хоче дiзнатися у вас: яку максимальну кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які цифри з набору, вибрати їхнiй порядок та скласти число з цих цифр. Звернiть увагу, що ви не зобов’язанi використати всi цифри. Ви ж не можете вiдмовити Вусу? :)

Маленька пiдказка вiд Математичної Сови:

  • Остача (залишок) вiд дiлення на число дорiвнює остачi вiд дiлення суми цифр числа на число 3.

  • Число є кратним числу (тобто дiлиться на b) лише, якщо остача вiд дiлення числа на число дорiвнює 0.

Технічні умови Програма Newnumbers читає з пристрою стандартного введення у першому рядку мiстить одне цiле число (1 ⩽ n⩽5 · 105) — кiлькiсть цифр. У другому рядку записано ц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.

У другому прикладі з цього набору ми можемо скласти максимум чисел. Один iз можливих способів — це скласти такі числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться цифри 11.

© LIKT 1998-2018