Problem Description

Xiao C has $n$ books, each with a weight. He decides to merge them into one pile.

In each merge, Xiao C can put one pile of books on top of another pile, so that they become one pile. If Xiao C puts the $i$-th pile onto the $j$-th pile, the stamina cost is the weight of the $i$-th pile plus the sum of the wear values of the two piles.

Initially, each book forms its own pile and all wear values are $0$. Each time Xiao C merges two piles, the new pile’s wear value becomes twice the larger wear value of the two piles plus one, and its weight becomes the sum of the weights of the two piles.

Your task is to design the merging order to minimize Xiao C’s stamina cost, and output this minimum cost.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $t$, the number of test cases.

Then for each test case:

The first line contains a positive integer $n$, meaning there are $n$ books.

The second line contains $n$ positive integers; the $i$-th number $w_i$ is the weight of the $i$-th book.

Output Format

For each test case, output one integer per line, representing the minimum stamina required to merge the $n$ books into one pile.

1
4
1 1 1 1

6

见附件中的 book/book2.in。

见附件中的 book/book2.ans。

见附件中的 book/book3.in。

见附件中的 book/book3.ans。

见附件中的 book/book4.in。

见附件中的 book/book4.ans。

Hint

[Sample Explanation #1]

If Xiao C first merges the $4$ books in pairs, and then merges the two resulting piles into one pile, then the stamina costs of the first two merges are both $1$. For the third merge, he puts a pile of weight $2$ onto the other pile; both piles have wear value $1$, so the stamina cost is $2 + 1 + 1 = 4$.

Therefore, under this plan, Xiao C’s total stamina cost is only $1 + 1 + 4 = 6$.

It can be proven that, in the above example, $6$ is the minimum stamina cost.

[Constraints]

For all test cases: $1 \le t \le 10$, $1 \le n \le 100$, $1 \le w_i \le 10 ^ 9$.

Special property: it is guaranteed that $w_i = 1$.

Translated by ChatGPT 5