Problem G
Lopsided Lineup

(from WikiMedia Commons)
Together with your coworker, Sergey, you are organizing the exciting Billiards and Pool Competition for your coworkers in your small company. However, communication has not been great between you two. You are not sure you and Sergey think alike, but as far as you are concerned, this would be a great opportunity to do some team building. The actual prizes are meaningless, but there is possibly a lot to be gained from this in team bonding. You want to maximise result.
You start reading some pseudo-scientific books on team management, and after some research, you conclude that there are two good ways of team bonding: people feel more connected after either a triumphant victory or a crushing defeat. This gives you a great idea: if you divide your coworkers into two groups that are as far apart in skill level as possible, both teams will experience improved bonding! You therefore think it is optimal to try to make the teams as unbalanced as possible. Make sure, however, that the teams are of equal size.
With a bit of work you come up with a nice model for the
strength of a team. You think team strength is mainly
determined by how well two players play together, whether they
encourage one another and complement each other’s weaknesses.
Whenever two players
Input
The input consists of:
-
One line with an even integer
( ), the total number of players. -
lines, the th of which contains integers ( ).For any
and , it is guaranteed that and .
Output
Output the maximum possible difference in strength between two teams of equal size.
Sample Input 1 | Sample Output 1 |
---|---|
6 0 4 -6 2 3 -3 4 0 2 -6 0 0 -6 2 0 0 2 2 2 -6 0 0 -1 5 3 0 2 -1 0 -4 -3 0 2 5 -4 0 |
0 |
Sample Input 2 | Sample Output 2 |
---|---|
4 0 1 2 2 1 0 8 -3 2 8 0 5 2 -3 5 0 |
6 |