У Джеффа есть n карточек, на каждой карточке нарисована либо цифра 0, либо цифра 5. Джефф может выбрать некоторые карточки и выложить их в ряд — получится некоторое число. Какое максимальное число, делящееся на 90, Джефф может выложить из имеющихся у него карточек?
Выложенное число не должно содержать лидирующих нулей, при этом считается, что число 0 не содержит лидирующих нулей. Джеффу не обязательно использовать все карточки.
Выходные данные
В единственную строку выведите ответ на задачу — максимальное число, которое делится на 90. Если из карточек нельзя составить ни одно число, которое делится на 90, выведите -1.
Примечание
В первом тесте единственное число кратное 90, которое можно сложить — это 0.
Во втором тесте можно сложить число 5555555550, оно кратно 90.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 0 5 0
|
0
|
|
2
|
11
5 5 5 5 5 5 5 5 0 5 5
|
5555555550
|