All submissions for this problem are available.
You have successfully completed your juggling performance, albeit with some errors. These mistakes have made the children in the crowd unhappy. To make them happy, the circusmaster has ordered the injured head clown to distribute candy among the children.
The clown finds out that the children in the crowd are spoilt brats and wont be happy receiving just 1 candy. The circus has N different kinds of candies. The amount of candies of each type will be told by the circusmaster. To satisfy the children, the clown needs to give each child 3 candies. Furthermore, all 3 candies cannot be of the same kind.
The circusmaster wants the clown to maximize the number of children that can be made happy. Now, the clown being the thick headed man he is, asks for your help. Help the clown solve this problem.
The first line of contains 1 integer T(the number of test cases). Each test case is defined by two lines.
The first line of each test case contains 1 integer N which signifies the number of kinds of candies.
The next line contains N integers Mi which signify the number of candies of each type the circus has.
For each of the T test case, output the maximum number of children that can be satisfied by the clown.
1 ≤ T ≤ 104
1 ≤ N ≤ 105
1 ≤ N×T ≤ 4×106
1 ≤ Mi ≤ 109, where Mi is the frequency of each kind of candy.
3 4 1 2 3 4 3 1 2 3 3 4 4 1
3 2 3
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, RUBY, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.