BPC 1 J3 - Group Project

View as PDF

Submit solution


Points: 5
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

You are a teacher deciding on pairs for a group project. You have 2N students that are given a quality score q_i. For each pair, you will receive X complaints, where X is the difference in quality between the two students. Output the minimum number of complaints you can receive.

Constraints

1 \le N \le 10^6

1 \le q_i \le 10^9 for all integer i from 1 to 2N.

Input Specification

The first line contains an integer, N.

The second line contains 2N integers, the i^\text{th} being q_i.

Output Specification

Output a single line containing an integer, the number of complaints if you optimally pair students to minimize complaints.

Note: the answer might not fit in a 32-bit integer.

Sample Input

3
1 7 4 6 10 9

Sample Output

5

Comments

There are no comments at the moment.