Крошка Тина устраивает чаепитие для трех своих кукол. У нее есть n конфет, для каждой из которых Тина знает ее параметр "шоколадности".
Тина хочет честно разделить конфеты между куклами, а именно, необходимо распределить их так, чтобы разница между наибольшей суммарной шоколадностью и наименьшей была минимально возможной.
При этом каждую конфету нужно отдать одной из трех кукол.
Входные данные
Первая строка содержит натуральное число n (1 <= n <= 12) - количество конфет у Тины.
Вторая строка содержит n натуральных чисел a
i, разделенных пробелами - параметры "шоколадности" каждой конфеты. 1 <= a
i <= 100.
Выходные данные
Выведите одно число - минимально возможную разницу между наибольшей суммарной шоколадностью и наименьшей.
Примечание
В первом тестовом примере можно отдать первые две конфеты первой кукле, третью и пятую второй кукле и четвертую третьей кукле. Тогда суммарные шоколадности будут равны 3, 2 и 3 соответственно. Разница между наибольшей и наименьшей равна 3 - 2 = 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 1 3 1
|
1
|