CodeChef - Suraj goes shopping

https://www.codechef.com/problems/ANUBTG

It is winter super sale and all the shops have various offers. Suraj selected N items to buy and he is standing in the billing queue. It was then he noticed the offer "Buy two, get two". That means for every two items you buy, they give you two items for free. However, items can be of varying price, they always charge for 2 most costly items and give other 2 as free. For example, if the items cost 1, 1, 2, 2, then you have to pay 4 and take all 4 items.

Suraj is busy reordering his items to reduce the total price he has to pay. He can separate the items and get them on different bills if needed. Can you tell me what is the least price Suraj has to pay to buy all the Nitems?

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. First line of each test case has single integer N. Second line of each test case has N space separated integers, which are the costs of items Suraj want to buy.

Output

For each test case, output a single line containing the required answer.

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ N ≤ 1000
• 1 ≤ Cost of items ≤ 1000

Example

Input:
3
4
1 1 2 2
2
10 200
7
1 1 10 2 2 2 1

Output:
4
210
14

Explanation

Example case 1

Suraj pays for 2 costly items and gets other 2 for free.

Example case 2

Suraj has to pay for both the items, he wont get anything for free.

Example case 3

Suraj separates the items into 2 bills. In one bill he pays 12. And in another bill he pays 2.

http://letuscode.in/index.php/2016/07/19/billing-algorithm/

A garments shop has “Buy 2, Get 2” offer for it’s customers. Whatever the items may be, they charge for costliest items from an order and give the cheapest ones free.
However we can divide the items into multiple orders to save more.

For example, Let us say we have 6 items with prices 200, 600, 100, 900, 800, 700. If we take them as one order, we will have to pay 3000.

6 items are divided into two groups {900,800,200,100}, {700,600} because they charge for highest price items. So the total bill would be 900+800+700+600 = 3000
Suppose we divide the items into two groups {900,800,700,600}, {200,100} we need to pay only900+800+200+100 = 2000

Now the problem is, given a list of prices, how do we calculate the minimum amount we need to pay?

This is a simple greedy algorithm. We just need to sort all the prices in descending order and group them into 4 per order. The last order might contain less than 4 items.

int main() {

int t;

cin >> t;

while( t-- ) {

   int n;

   cin >> n;

   vector<int> prices(n);

   int i;

   for(i = 0; i < n; i++)

   {

       cin >> prices[i];

   }

   sort( prices.begin(), prices.end(), greater<int>());

   int amt = 0;

   for(i = 0; i <= n-2; i+=4)

   {

       amt += prices[i]+prices[i+1];

   }

   if(i == n-1)

       amt += prices[n-1];

   cout << amt << endl;

}

return 0;

}