Bridge

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
#include <time.h>
#include <set>
using namespace std;


#ifdef mycom
#include <fstream>
ifstream fin("input");
#else
#define fin cin
#endif

vector<int> A;
vector<int> B;

 

 


int main()
{
 int testcase;

 testcase = 1;
 fin >> testcase;

 int hours;
 string solution; 
 solution.resize(10000);
 for(int i=1; i<=testcase; i++)
 {
  solution = "";

  hours = 0;
  int n;
  fin >> n;

  for(int j=1; j<=n; j++)
  {
   int temp;
   fin >> temp;
   A.push_back(temp);
  }

  sort(A.begin(), A.end());
  //saram 에 대한 처리가 들어감
  while(A.empty() == false)
  {
   if(A.size() == 1)
   {
    vector<int>::iterator b = A.begin();
    int _A = *b;

    B.insert(B.begin(), A.begin(), A.end());
    A.clear();

    char buf[256];
    sprintf(buf, "%d\n", _A);
    solution += buf;
    hours += _A;
   }
   else if(A.size() == 2)
   {
    vector<int>::iterator b = A.begin();
    int _A = *b;
    b++;
    int _B = *b;

    B.insert(B.begin(), A.begin(), A.end());
    A.clear();
    char buf[256];
    sprintf(buf, "%d %d\n", _A, _B);
    solution += buf;
    hours += _B;
   }
   else if(A.size() == 3)
   {
    vector<int>::iterator b = A.begin();
    int _A = *b;
    b++;
    int _B = *b;
    b++;
    int _C = *b;


    B.insert(B.begin(), A.begin(), A.end());
    A.clear();
    char buf[256];

    sprintf(buf, "%d %d\n", _A, _B);
    solution += buf;

    sprintf(buf, "%d\n", _A);
    solution += buf;

    sprintf(buf, "%d %d\n", _A, _C);
    solution += buf;
    hours += _A + _B + _C;
   }
   else if(A.size() >= 4)
   {
    vector<int>::iterator b = A.begin();
    vector<int>::reverse_iterator rb = A.rbegin();
    int _A = *b;
    b++;
    int _B = *b;
    int _Z = *rb;
    rb++;
    int _Y = *rb;

    A.erase(find(A.begin(), A.end(), _Y));
    A.erase(find(A.begin(), A.end(), _Z));
    //A.erase(_Y);
    //A.erase(_Z);
    B.push_back(_Y);
    B.push_back(_Z);
    if(_A + 2*_B + _Z <= 2*_A + _Y + _Z)
    {    
     char buf[256];
     sprintf(buf, "%d %d\n", _A, _B);
     solution += buf;
     sprintf(buf, "%d\n", _A);
     solution += buf;
     sprintf(buf, "%d %d\n", _Y, _Z);
     solution += buf;
     sprintf(buf, "%d\n", _B);
     solution += buf;

     hours += _A + 2*_B + _Z;
    }
    else
    {
     char buf[256];
     sprintf(buf, "%d %d\n", _A, _Z);
     solution += buf;
     sprintf(buf, "%d\n", _A);
     solution += buf;
     sprintf(buf, "%d %d\n", _A, _Y);
     solution += buf;
     sprintf(buf, "%d\n", _A);
     solution += buf;
     hours += 2*_A + _Y + _Z;
    }
   }
   sort(A.begin(), A.end());
   sort(B.begin(), B.end());
  }
  cout << hours <<endl << solution;
  if(testcase  != i)
   cout << endl;
 }

 return 0;
}