19. 煉金術

煉金術

題目敘述

愛德華是一個煉金術師，他會各式各樣的煉金術，而煉金術能將兩種物質合成出一種新物質，根據質量守恆定理，新物質的質量會等於兩種物質的質量和，但這樣需要消耗時間，所消耗的時間等於新物質的質量和。

今天，愛德華拿到了很多種物質，每種物質都有自己的質量，想要將它們全部合成在一起，這樣相當花時間，愛德華相信透過不同順序的合成，消耗的時間也會不同，希望你幫幫他算出這樣最少要花多少時間。

輸入說明

第一行有一個數字$T(T \leq 10)$，代表測資數， 接下來每個測資，第一行有一個數字N，代表物質的數量， 第二行有N個數字，代表物質的質量，質量皆不超過$10^{12}$。

輸出說明

對於每筆測資，輸出一行最少花費的時間。

範例輸入

2 3 2 3 5 4 4 5 6 7

範例輸出

15 44

子題一[20%]

$N \leq 10$

子題一[20%]

$N \leq 1000$

子題一[20%]

$N \leq 100000$

Judge Setting

run-time limit: 1000 ms
memory limit: 104857600 byte
測資數量: 4