Maximizing Good Numbers

We call an integer a good number if, when written in its usual decimal representation, it contains no fewer than \(6\) digits \(6\). For example, \(666666\) and \(162636465666\) are good numbers, while \(12366666\) is not.

You are given \(n\) positive integers \(a_i\). You may partition these numbers into several groups and then concatenate the numbers within each group in an arbitrary order. However, each group may contain at most \(3\) numbers. A group is considered to form a good number if the concatenation (i.e. the string obtained by writing the numbers one after the other) contains at least \(6\) occurrences of the digit \(6\) (note that the order of digits is preserved in the concatenation).

Determine the maximum number of good numbers that can be obtained by an optimal grouping.

Note: A number that is already good (i.e. contains at least \(6\) occurrences of \(6\)) may be taken as a group by itself.

inputFormat

The first line contains a single integer \(n\) (the number of positive integers). The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single integer representing the maximum number of good numbers that can be obtained.

sample

3
666666 123 666

1