**Valentine Vex solution codechef** – Alice and Bob play a game on an array of NN integers. They alternate moves, with Alice making the first move.

## [Solution] Valentine Vex solution codechef

The rules are as follows:

- On
**their first move**, a player can pick**any**element in the array, add its value to their score, and then**remove**it from the array. - On a move that is
**not their first move**, the player should pick an element with the**opposite parity**of the element chosen on**their previous move**, add its value to their score, and then**remove**it from the array. - If a player cannot make a move, either because the array is empty or it doesn’t contain an element of the parity they need, the player skips their turn.
- The game ends when both players are unable to move.

Note that the parity of an element chosen by a player depends only on the parity of their own previously chosen element — it does not depend on what their opponent last chose.

Determine the optimal score of Alice if both players play optimally, each attempting to **maximize** their own score. If there are multiple ways to obtain maximum score for themselves, the players will adopt a strategy that will **maximize** the score of their opponent whilst obtaining their maximum score themselves.

Note that it is not necessary to use all the elements in the array.

### Input Format

- The first line of input will contain a single integer TT, denoting the number of test cases. Then the test cases follow.
- Each test case consists of two lines of input.
- The first line of each test case contains one integer NN — the size of the array AA
- The second line of each test case contains NN space-separated integers, denoting the array elements.

### Output Format

For each test case, output on a new line the optimal score achieved by Alice.

## [Solution] Valentine Vex solution codechef

- 1≤T≤2⋅1041≤T≤2⋅104
- 2≤N≤1052≤N≤105
- 1≤Ai≤1061≤Ai≤106
- Sum of NN across all test cases won’t exceed 2⋅1052⋅105

### Sample Input 1

```
3
4
1 2 3 4
3
45 10 53
6
7 5 2 2 6 2
```

### Sample Output 1

```
5
55
15
```

## Valentine Vex solution codechef Explanation

**Test case 11:** Under optimal play, Alice’s maximum score is 55. One sequence of moves leading to this score is:

- On her first move, Alice picks 44.
- On his first move, Bob picks 33.
- On her second move, Alice must choose an
*odd*number, since she previously picked an even number. So, Alice’s only choice is to pick 11. - On his second move, Bob picks 22, since he must choose an
*even*number and it is the only one left.

Alice’s score is thus 4+1=54+1=5. Note that this is not the only optimal strategy — however, any other strategy where both players play optimally will still lead to Alice having a score of 55.

**Test case 22:** Alice’s strategy is as follows:

- On her first move, Alice picks 1010.
- On his first move, Bob picks 5353.
- Finally, Alice picks 4545, ending up with a score of 10+45=5510+45=55.

Note that if Alice picks either 5353 or 4545 on her first move, Bob will pick 1010 on his move. This leaves Alice unable to make a move, so she skips her turn and Bob picks the remaining number, leaving Alice with a score strictly smaller than 5555.

**Test case 33:** Alice picks 6,7,6,7, and 22 for a score of 1515, while Bob picks 2,5,2,5, and 22 for a score of 99. Note that Bob can also achieve a score of 99 by picking 77 and 22 and then skipping his third move, but he won’t do this because it would lead to Alice only reaching a score of 1313 — as mentioned earlier, a player attempts to maximize their own score, and then **maximize** their opponent’s score.