Bridge/권영기

#include<stdio.h>
#include<memory.h>
#include<algorithm>
#include<queue>
using namespace std;
#define N 1020
queue < pair< int, int> > ans2;
int main(void)
{

//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);

	int t, n, tempn, p, ans = 0;
	int man[N];
	scanf("%d", &t);

	for(int i = 0; i<t; i++){
		scanf("%d", &n);
		memset(man, 0, sizeof(int) * N);
		ans = 0;
		for(int j = 0; j<n; j++){
			scanf("%d", &man[j]);
		}
		sort(man, man + n);
		tempn = n;
		p = n-1;

		while(tempn > 0){
			if(tempn >= 4){
				if(man[0] + man[1] + man[p] + man[1] > man[p] + man[0] + man[p-1] + man[0]){
					ans += man[p] + man[0] + man[p-1] + man[0];
					ans2.push(make_pair(man[0], man[p]));
					ans2.push(make_pair(man[0], -1));
					ans2.push(make_pair(man[0], man[p-1]));
					ans2.push(make_pair(man[0], -1));
				}
				else{
					ans += man[0] + man[1] + man[p] + man[1];
					ans2.push(make_pair(man[0], man[1]));
					ans2.push(make_pair(man[0], -1));
					ans2.push(make_pair(man[p-1], man[p]));
					ans2.push(make_pair(man[1], -1));
				}
				tempn -= 2;
				p -= 2;
			}
			else{
				if(tempn == 3){
					ans += man[0] + man[p] + man[1];
					ans2.push(make_pair(man[0], man[p]));
					ans2.push(make_pair(man[0], -1));
					ans2.push(make_pair(man[0], man[1]));
					tempn = 0;
				}
				else if(tempn == 2){
					ans += man[1];
					ans2.push(make_pair(man[0], man[1]));
					tempn = 0;
				}
				else if(tempn == 1){
					ans += man[0];
					ans2.push(make_pair(man[0], -1));
					tempn = 0;
				}
			}
		}

		printf("%d\n", ans);
		while(!ans2.empty()){
			pair <int, int> temp;
			temp = ans2.front();
			ans2.pop();
			printf("%d", temp.first);
			if(temp.second != -1)printf(" %d", temp.second);
			printf("\n");
		}
		if(i != t-1)printf("\n");
	}


}