經典的貪心算法，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1700
//經典的貪心題目，當人數大于4人時有兩種走法，取最優的一種
#include <stdio.h>
#include <stdlib.h>

const int LEN = 1005; 

int people[LEN];

int cmp ( const void *a, const void *b )
{

    return *( (int *)a )-*( (int *)b );
}

int work ( int n )
{

    qsort ( people, n, sizeof ( int ), cmp );
    int time = 0;
    int last = n;
    while ( last )
    {
        if ( last==1 )
        {
            time += people[last-1];
            last -= 1;
            continue;
        }
        if ( last==2 )
        {
            time += people[last-1];
            last -= 2;
            continue;
        }
        if ( last==3 )
        {
            time += people[last-1]+people[last-2]+people[last-3];
            last -= 3;
            continue;
        }

        int one = people[0]+people[last-1]+people[0]+people[last-2];
        int two = people[1]+people[0]+people[last-1]+people[1];
        if ( one>two )
        {
            time += two;
        }
        else
        {
            time += one;
        }
        last -= 2;
    }
    return time;
}

int main ()
{

    int t;
    int n;

    scanf ( "%d", &t );
    while ( t -- )
    {
        scanf ( "%d", &n );
        for ( int i=0; i<n; i++ )
        {
            scanf ( "%d", &people[i] );
        }

        printf ( "%d\n", work ( n ) );
    }
    return 0;
}