Шеф-повар Ада готовит N блюд (пронумерованных от 1 до N). Для каждого действительного i на приготовление i-го блюда уходит Ci минут. Блюда можно готовить в любом порядке.

У Ады есть кухня с двумя одинаковыми конфорками. На каждое действительное ii для приготовления i-го блюда она ставит его на одну из конфорок и через Ci минут снимает с этой конфорки; блюдо нельзя снимать с конфорки до истечения этих минут CiCi, иначе оно остынет и испортится. Любые два блюда могут быть приготовлены одновременно, однако никакие два блюда не могут находиться на одной и той же конфорке одновременно. Ада может снять тарелку с конфорки и одновременно поставить другую тарелку на ту же конфорку.

Какое минимальное время необходимо для приготовления всех блюд, т.е. до состояния, когда все блюда готовы?

Вход

  • Первая строка входных данных содержит единственное целое число T, обозначающее количество тестовых случаев. Ниже приводится описание T тестовых случаев.
  • Первая строка каждого набора входных данных содержит одно целое число N.
  • Во второй строке через пробел записаны N целых чисел C1, C2,…, CN.

Вывод

Для каждого набора входных данных выведите одну строку, содержащую одно целое число ― минимальное количество минут, необходимое для приготовления всех блюд.

Ограничения

  • 1≤T≤1,000
  • 1≤N≤4
  • 1≤Ci≤5 для каждого действительного i

Подзадачи

Подзадача №1 (1 балл): C1=C2=…=CN

Подзадача 2 (99 баллов): исходные ограничения.

Пример ввода

3
3
2 2 2
3
1 2 3
4
2 3 4 5

Пример вывода

4
3
7

Объяснение

Пример 1: поставьте первые две тарелки на конфорки, подождите две минуты, уберите обе тарелки и приготовьте последнюю на одной конфорке.

Пример 2. Поставьте первую и третью тарелки на конфорки. Когда первое блюдо будет готово, снимите его, а второе поставьте на ту же конфорку.

Пример 3: поставьте третью и четвертую посуду на конфорки. Когда третье блюдо будет готово, снимите его и поставьте второе блюдо на ту же конфорку. Точно так же замените четвертое блюдо (когда оно будет приготовлено) первым блюдом на другой конфорке.

Решение

#include <iostream>
using namespace std;
void swap(int *xp, int *yp) 
{ 
    int temp = *xp; 
    *xp = *yp; 
    *yp = temp; 
}
void selectionSort(int arr[], int n) 
{ 
    int i, j, min_idx; 
  
    // One by one move boundary of unsorted subarray 
    for (i = 0; i < n-1; i++) 
    { 
        // Find the minimum element in unsorted array 
        min_idx = i; 
        for (j = i+1; j < n; j++) 
          if (arr[j] > arr[min_idx]) 
            min_idx = j; 
  
        // Swap the found minimum element with the first element 
        swap(&arr[min_idx], &arr[i]); 
    } 
}
/* void printArray(int arr[], int n)  
{  
    int i;  
    for (i = 0; i < n; i++)  
        cout << arr[i] << " ";  
    cout << endl; 
}  */
  
int main() {
    int T,N,TT[4];
 cin >> T;
  int k = T;
 while(k--){
     cin >> N;
      for( int i = 0; i < N; i++)
             cin>>TT[i];
 
 
 selectionSort( TT,N);
// printArray( TT, N);
 
 int b1=0,b2=0;
  for(int i= 0; i< N; i++){
     
 if(b1==b2)
   b1 += TT[i]; 
 else if (b1>b2)
   b2 += TT[i];
 else if(b2>b1)
   b1 += TT[i];
  }
 
   cout << max(b1,b2)<< endl;
 }
 return 0;
}