No submission language available for this problem.

Background

Special for beginners, ^_^

Description

在一个古老的村庄里，冒险家被困在一座孤岛上。他们需要合作通过一座河才能返回大陆。然而，们只有一艘破旧的小船，为了避免河中的危险怪物，这艘小船一次最多只能搭载两个人。现已知没人单独过河的时间，且一起坐船过河的速度将由两人中的慢者决定，问他们所有人全部过河返回大陆所需最短时间。

Format

Input

输入 t 组数据，每组数据第 1 行输入 n，第 2 行输入 n 个数，表示每个人过河的时间。

Output

输出t行数据，每行1个数，表示每组过河最少时间。

Samples

1
4
1 2 5 10

17

Limitation

1 ≤ n ≤ 10000