Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Crisis in Antartica

Limits: 16s, 32 MB

Mr X and Y are famous chemists and mathematicians who live in Antartica. You know, it’s a cold place and temperature often go below freezing point. Suddenly, one day a crisis came to Mr X and Y and their neighbourhood. Their gas and electricity supply suddenly cut-off for some reason and there was a huge storm coming to them. Mr X and Y being gifted chemists quickly thought of a solution for their heat source and water supply. Their lab had huge collections of fully concentrated hydrochloric acid and Sodium Hydroxide base. They said to their neighbours, “Fear not! We can make heat and water from acid and base. Thus both heat source and water shortages can be met”. If you have forgotten some basics, then for your information reaction between acid and base is an exothermic reaction. Products of this reaction are salt and water and some heat which is equal to 57.3 KJ/mol. A curious science enthusiast among the neighbours asked, “How many KiloJoule of heat can you produce at max?”. Mr X and Y began to wonder how will they solve such a problem without a computer. Can you help them by calculating the maximum heat that can be produced?

For simplicity, consider they have N containers each of which has a capacity of ai moles which you can only fill with acid or base or keep empty. You have enough Hydrochloric acid and Sodium Hydroxide to fill all the containers. Till now the problem was simple but the science enthusiast had a request, “Water should maintain PH of 7”. Or in other words, you need to have an equal amount of acid and base (measured in mole). Now, find the maximum amount of heat that can be produced.

Input

Input begins with the number of test cases, T (0 < T < 101). Each case begins with an integer N (0 < N < 101) representing the number of containers. Next, N integers represent capacity of N containers as a1, a2, …. aN. Capacity of each container will be more than zero and less than 500001 and total capacity of all containers will not exceed 500000.

Output

For each case print the case number and the desired result.

Samples

InputOutput
4
3
3 4 7
3
10 9 2
2
21 21
9
15 15 14 24 14 3 20 23 15
Case 1: 401.1
Case 2: 0.0
Case 3: 1203.3
Case 4: 3667.2

Author
Discussion
Submit

Login to submit