Best Pairing

Difficulty: 1400 3000 ms 128 MB

greedy sorting

N is even. Split the values into N/2 pairs so that the sum of the pair products is as large as possible. Print that maximum.

Input: the first line has N (even); the second line has N integers.

Output: the maximum possible sum of pair products.

Constraints:

• 2 ≤ N ≤ 10⁵
• −100 ≤ a_i ≤ 100

Sample Tests

4
1 2 3 4

14

4
-3 -4 1 2

14

Read the Editorial