AlgoLiga 2018

Bitomir, jako tzw. "thrill-seeker", postanowił na koniec wakacji udać się do dżungli znajdującej się na wschodniej granicy Bitocji w poszukiwaniu przygód. Ci z Was, którzy słyszeli o tej sławnej formacji roślinnej domyślają się, że Bitomir nie wróci zawiedziony ze swojej wycieczki. I mają rację! Już drugiego dnia pobytu, Bitomir wraz z towarzyszami natknęli się na stado dzikich χ-popotamów. Zaczęli przed nimi uciekać, ale napotkali przeszkodę - rzekę ξ-ngu. Cofnąć się nie mogą, z boków również powoli zbliżają się te wielkie zwierzęta. Nie pozostało nic, jak przeprawić się przez rzekę. Na szczęście rzeka jest płytka i sięga do pasa, a nurt nie jest zbyt silny, więc spokojnie będzie można przez nią przejść. Zaraz po wejściu do wody, kolega Bitomira wyskoczył z niej jednak z wrzaskiem. Okazało się, że w wodzie są π-ranie! Całe szczęście, że każdy ma przy sobie kombinezon zabezpieczający przed ich ostrymi zębami. Bitomir wyciągnął swój kombinezon i spostrzegł, że wszyscy na niego patrzą. Niestety, wyszło na to, że wszyscy pozostali towarzysze porzucili swoje plecaki by móc szybciej uciekać przed χ-popotamami. Co tu robić‽

Po chwili, Bitomir wpadł na pomysł, że jedna osoba będzie nakładać strój, brać na ręce inną, przeprawiać się na drugą stronę, a następnie jedna z nich wróci w kombinezonie. Czynności te wykonywane będą aż wszyscy znajdą się po drugiej stronie ξ-ngu. Oczywiście na obu stronach człowiek noszący kombinezon może się zmieniać, bo jak zminimalizować sumaryczny czas przeprawy wszystkich na drugi brzeg. Każda z osób porusza się ze stałą jej prędkością. Dodatkowo, im dana osoba jest wolniejsza, tym jest silniejsza. Wynika z tego, że gdy dwie osoby przemieszczają się na drugi brzeg, wolniejsza niesie szybszą. A zatem, czas przeprawy dwóch osób jest równy czasowi, który wolniejsza osoba poświęciłaby na przejście przez rzekę w pojedynkę (niesienie kolegi ich na szczęście nie spowalnia).

Jako kolega Bitomira, oblicz ile minimalnie czasu potrzeba by przeprawić wszystkich na drugi brzeg. Jeśli okaże się, że czas ten będzie za długi, będziecie musieli wspiąć się na cienkie drzewa. Pospiesz się!

Wejście

W pierwszej linii wejścia znajduje się liczba testów t (0 < t ≤ 10⁴). Pierwsza linia każdego testu zawiera liczbę n (1 ≤ n < 10⁷) oznaczającą ilość towarzyszy Bitomira (włącznie z nim). Druga i ostatnia linia każdego testu zawiera n liczb z przedziału 1..10⁴, oznaczająca ilość czasu, która jest potrzebna danej osobie do pokonania rzeki.

Uwaga: W przypadku użycia strumieni proszę rozważyć skorzystanie z funkcji sync_with_stdio.

Wyjście

Dla każdego testu jedna liczba będąca minimalną ilością czasu, potrzebnego na przeprawę wszystkich poszukiwaczy wrażeń na drugą stronę.

Przykład

Wejście:
1
5
1 3 8 6 12

Wyjście:
29

Wyjaśnienie przykładu:

Jest 5 osób. By przeprawić się jak najszybciej najpierw przejdzie osoba nr 1 i nr 2. Osoba nr 2 wraca. Następnie osoby nr 3 i 5. Osoba nr 1 wraca. Potem osoby nr 4 i 1. Osoba nr 1 wraca. Na koniec pozostałe osoby: nr 1 oraz 2. Łączny czas to 3+3+12+1+6+1+3=29.