Koło Naukowe TWIPS

W pewnej firmie informatycznej znajdują się serwery gromadzące duże ilości danych. W związku z przebudową infrastruktury technicznej podjęto decyzję o przeniesieniu i umieszczeniu danych na jednym serwerze. Każde dwa serwery połączone są bezpośrednim łączem. Każdy z serwerów w danym momencie może albo wysyłać dane tylko do jednego serwera, albo odbierać dane tylko od jednego serwera. Każdy serwer może pomieścić dane znajdujące się na wszystkich serwerach. Cała operacja przenoszenia danych powinna zostać przeprowadzona tak, aby trwała jak najkrócej. Czas przenoszenia 1MB danych pomiędzy dwoma serwerami jest stały i wynosi 1s.

Zadanie

Napisz program, który dla zadanej konfiguracji serwerów (rozmiar przechowywanych danych) wyznaczy minimalną liczbę sekund, potrzebnych do wykonania tej operacji.

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów danych C (1 ≤ C ≤ 100). W kolejnych wierszach wejścia znajdują się zestawy danych. Każdy z C zestawów danych składa się z dwóch wierszy. Pierwszy wiersz zestawu zawiera liczbę naturalną n określającą liczbę serwerów (1 ≤ n ≤ 100). Drugi wiersz zestawu danych zawiera n liczb całkowitych: a₁, ..., a_n, oddzielonych pojedynczą spacją. Liczba a_i (i = 1, ..., n; 0 ≤ a_i < 2³¹) określa rozmiar danych w MB przechowywanych przez i-ty serwer.

Wyjście

Dla każdego zestawu danych, w kolejnych liniach wyjścia, należy wypisać minimalną liczbę sekund potrzebnych do wykonania operacji przenoszenia danych na jeden serwer.

Przykład

Dla danych wejściowych:

2
4
4 10 8 3
2
1 1

poprawną odpowiedzią jest:

15
1