A drone-repair depot has just pulled 2n used battery cells out of returned drones, each cell labeled with its remaining charge (a non-negative integer). Every cell must go into exactly one of n dual-cell packs, using all 2n cells with none left over. A pack is only as strong as its weaker cell: the usable output of a pack equals the SMALLER of the two charge values placed into it. The depot manager wants to choose the pairing of all 2n cells into n packs that maximizes the sum of usable outputs across all n packs. Compute that maximum possible total.
Line 1: a single integer n — the number of packs to build.
Line 2: 2n space-separated integers c_1 ... c_{2n} — the charge levels of the 2n cells, in the order they were pulled off the shelf.
Print a single integer: the maximum possible sum, over all ways to pair up the 2n cells into n packs, of the smaller charge value in each pack.
1 <= n <= 100000 <= c_i <= 10000Example 1
Input
2 1 4 3 2
Expected
4
Explanation
Sorting the four cells gives 1, 2, 3, 4. Pairing the two smallest together and the two largest together — (1,2) and (3,4) — yields usable outputs 1 and 3, for a total of 4. No other pairing of these four cells reaches a higher total.
Example 2
Input
3 6 2 6 5 1 2
Expected
9
Explanation
Sorted, the six charges are 1, 2, 2, 5, 6, 6. Pairing consecutive sorted cells — (1,2), (2,5), (6,6) — gives usable outputs 1, 2, 6, for a total of 9, which is the best achievable pairing of these cells.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →