Problem
Little Tina is hosting a tea party for her three dolls. She has n chocolates, for each of which Tina knows her "chocolate" parameter.
Tina wants to fairly distribute the candies between the dolls, namely, it is necessary to distribute them so that the difference between the highest total chocolate content and the lowest is as small as possible.
In addition, each candy must be given to one of the three dolls.
Input:
The first line contains a natural number n (1 <= n <= 12) - the number of sweets Tina has.
The second line contains n natural numbers a
i separated by spaces - the "chocolateness" parameters; every candy. 1 <= a
i <= 100.
Output:
Print a single number - the minimum possible difference between the largest total chocolate content and the smallest one.
Example:
| Input |
Output |
5
1 2 1 3 1
| 1 |
Explanation:
You can give the first two candies to the first doll, the third and fifth to the second doll, and the fourth to the third doll. Then the total chocolate content will be equal to 3, 2 and 3, respectively. The difference between the largest and smallest is 3 - 2 = 1.