【題目描述】

有n??個(gè)人一條船，所有人要從左岸渡船到右岸，第i??個(gè)人過(guò)河時(shí)間是ai????。船上最多坐兩個(gè)人，船從右岸回到左岸時(shí)必須保證船上有人。每次船的行駛時(shí)間等于船上兩人中過(guò)河時(shí)間的較大值。

問(wèn)過(guò)河所需最短時(shí)間。

【輸入】

輸入t??組數據，每組數據第11行輸入n??，第22行輸入n??個(gè)數，表示每個(gè)人過(guò)河的時(shí)間。

【輸出】

輸出t??行數據，每行11個(gè)數，表示每組過(guò)河最少時(shí)間。

【輸入樣例】

1

4

1 2 5 10

【輸出樣例】

17