Lucky Number
Description
Matías has a deck of $N$ cards. Each card has an integer written on it. As his lucky number is five, he wants to form several groups with these cards in such a way that the sum of the numbers on the cards in each group is a multiple of five. No card can be in two or more groups. It is possible that some cards do not belong to any group. What is the maximum number of groups that Matías can form?
A line with an integer $N$ $(1 \leq N \leq 2 \cdot 10^5)$, the number of cards in Matías' deck.
Then, a second line with $N$ integers $C_1, C_2, \ldots, C_N$. Each one indicates the number written on the $i$-th card $(1 \leq C_i \leq 10^9)$.
A single line with a single integer, representing the maximum number of groups of cards that Matías can form.
Input
A line with an integer $N$ $(1 \leq N \leq 2 \cdot 10^5)$, the number of cards in Matías' deck.
Then, a second line with $N$ integers $C_1, C_2, \ldots, C_N$. Each one indicates the number written on the $i$-th card $(1 \leq C_i \leq 10^9)$.
Output
A single line with a single integer, representing the maximum number of groups of cards that Matías can form.
6
33 21 66 8 1 108
9
1 6 7 10 16 18 41 42 77
2
19 7
1
3
0
Note
In the first example, Matías can form a group with the following four cards: $33, 21, 8$, and $108$. Their sum is $33 + 21 + 8 + 108 = 170$ which is a multiple of five. Two groups of cards whose sum is a multiple of five cannot be formed.
In the second example, Matías can form three groups as follows:
- The first group contains the cards $1, 6, 41$, and $77$.
- The second group contains the cards $7$ and $18$.
- The third group contains the card $10$.