玩過《雷頓》就知道這題可以貪心
小等於2人：1,2->
3人時：
1,3->
1<-
1,2->
1<-
否則：
1，2->
2<-
max1,max2->
1<-
OR：
1,max1->
1<-
2,max2->
2<-
於是數據規模-2
[delphi]
Program P1700;
var
t,n,i,j:longint;
l,r:longint;
a:array[1..1000] of longint;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=a[(l+r) shr 1];
repeat
while (a[i]<m) do inc(i);
while (a[j]>m) do dec(j);
if i<=j then
begin
p:=a[i];a[i]:=a[j];a[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function max(a,b:longint):longint;
begin
if a<b then exit(b) else exit(a);
end;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
function ww(x:longint):longint;
var
i,j:longint;
begin
if x=1 then exit(a[1]);
if x=2 then exit(a[2]);
if x=3 then exit(a[1]+a[2]+a[3]);
i:=2*a[1]+a[x]+a[x-1];
j:=2*a[2]+a[1]+a[x];
exit(ww(x-2)+min(i,j));
//1,2-> 1< r1,r2-> 2<=
end;
begin
read(t);
while (t>0) do
begin
read(n);
for i:=1 to n do read(a[i]);
qsort(1,n);
l:=1;r:=n;
writeln(ww(n));
dec(t);
end;
end.
