haritha has n number of boxes containing a[i] chocolates .she want to pack all the chocolates in the n boxes
into one box. the shop keeper can pack 2 boxes into onebox at a time for that he demanded money equal to the
no of chocolates in both boxes. now haritha has to choose 2 boxes every time and give it to him such that she has to reduce the
amount payable to the shopkeeper.
input format:
first line consists of no of testcases(t).
for each testcases on first line no of boxes is given.
on second line no of chocolates in each box is given.
output format:
you need to print minimum payment she can pay to the shop keeper.
input constraints:
1<=t<=50
1<=n<=100
1<=a[i]<=100
use huffman coding
1st we merge 1 and 2 we get 3(s1)
then we merge 3(s1) and 3 we get 6(s2)
now we merge 5 and 6(s2) we get 11(s3)
now finally we merge 6 and 11(s3) we get 17(s4)
hence minimum cost is s1 + s2 + s3 + s4 = 3 + 6 + 11 + 17 = 37
