Chef And easy problem

 This was an easy one just like the name of the problem says, the problem statement is mentioned below and it is highly recommended to first try the Problem on your own before going to the solution part. Enjoy...

Problem Statement:-

Chef and Roma are playing a game. Rules of the game are quite simple. Initially there are N piles of stones on the table. In each turn, a player can choose one pile and remove it from the table. Each player want to maximize the total number of stones removed by him. Chef takes the first turn.

Please tell Chef the maximum number of stones he can remove assuming that both players play optimally.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the number of piles.

The second line contains N space separated integers A1, A2, ..., AN denoting the number of stones in each pile.

Output

For each test case, output a single line containg the maximum number of stones that Chef can remove.

Constraints

• 1 ≤ Ai ≤ 109
• Subtask 1 (35 points): T = 10, 1 ≤ N ≤ 1000
• Subtask 2 (65 points): T = 10, 1 ≤ N ≤ 105

Sample 1:

Input

Output

2
3
1 2 3
3
1 2 1

4
3

The below mentioned code was implemented fully in 10 mins, including the idea part too:-

for _ in range(int(input())):

    n=int(input())

    print(sum([sorted(list(map(int,input().split())))[i] for i in range(n-1,-1,-2)]))

       

Try to get the main idea of the logic instead of seeing the code blindly because

understanding the logic is what will make your concepts clear and remember we don't

solve problems to pass tests but we solve them to get more idea in our mind and make

our mind think in this era of Internet where we don't have to think about anything

and we just blindly search everything from the Internet, remember it won't be available

everywhere...

Good Night :)