12 коров Фермера Джона прибыли на зимние Му-олимпийские игры этого года, каждая с уровнем лыжного мастерства от 1 до 1,000,000.
ФД хочет разделить их на 4 команды по 3 так, чтобы получились команды, сбалансированные в смысле суммарного уровня мастерства (уровень мастерства команды определяется как сумма уровней мастерства коров в команде).
Точнее, он хочет минимизировать S – s, где S и s – максимальный и минимальный уровни мастерства команд. Это обеспечивает, что различие между самой сильной и самой слабой командой будет минимально.
Помогите ФД определить минимально возможное значение S-s.
PROBLEM NAME: bteams
Формат входных данных
* Строки 1..12: Каждая строка содержит уровень мастерства одной коровы.
Формат выходных данных
* Строка 1: минимально возможное значение S - s.
Примечание
Одно из возможных решений разделить коровы на команды так: (12,1,7), (9,8,3), (10,5,4), (11,2,6). У первых двух суммарный уровень мастерства 20, а у вторых двух – 19.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
2
3
4
5
6
7
8
9
10
11
12
|
1
|