402349: GYM100735 D Triangle Formation
Memory Limit:64 MB
Time Limit:0 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
D. Triangle Formationtime limit per test0.25 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output
You are given N wooden sticks. Your task is to determine how many triangles can be made from the given sticks without breaking them. Each stick can be used in at most one triangle.
InputThe first line of each test case contains the number of sticks N. (1 ≤ N ≤ 15)
The second line of each test case contains N integers leni that are the lengths of the sticks. (1 ≤ leni ≤ 109).
OutputOutput single integer R – the maximal number of triangles.
ExamplesInput2Output
1 1
0Input
3Output
2 2 2
1Input
6Output
2 2 3 4 5 6
2