A93164.「NOI2023」合并书本

小 C 有 $n$ 本书，每本书都有一个重量，他决定把它们合并成一摞。

每一次合并小 C 可以把一摞书放到另一摞书上面，使得它们合并到一摞。如果小 C 把第 $i$ 摞书放到第 $j$ 摞书上面，小 C 需要消耗的体力为第 $i$ 摞书的重量加上两摞书的磨损值之和。

初始时每本书自成一摞且磨损值均为 $0$。每当小 C 将两摞书合并后，形成的新的一摞书的磨损值为合并前的两摞书的磨损值的较大值的两倍再加一，重量为合并前的两摞书的重量之和。

你的任务是设计出合并的次序方案，使小 C 耗费的体力最少，并输出这个最小的体力耗费值。

从文件 book.in 中读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数 $t$，表示数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

输入的第一行包含一个正整数 $n$，表示有 $n$ 本书。

输入的第二行包含 $n$ 歌正整数，第 $i$ 个数 $w_i$ 表示第 $i$ 本书的重量。

输出到文件 book.out 中。

对于每组测试数据输出一行一个整数，表示将 $n$ 本书合并成一摞需要消耗的最少体力。

对于所有测试数据保证：$1 \le t \le 10$，$1 \le n \le 100$，$1 \le w_i \le 10 ^ 9$。

测试点编号	$n \le$	是否有特殊性质
$1 \sim 2$	$7$	否
$3$	$11$	否
$4$	$13$	否
$5 \sim 6$	$22$	否
$7 \sim 8$	$28$	否
$9 \sim 13$	$50$	否
$14$	$60$	否
$15$	$70$	否
$16$	$80$	否
$17 \sim 18$	$100$	是
$19 \sim 20$	$100$	否

特殊性质：保证 $w_i = 1$。