Как-то раз два
пирата нашли на острове клад. Клад состоит из N золотых слитков, для каждого
слитка известен его вес в граммах. Пираты решили разделить клад поровну.
Однако, у них возник вопрос: что делать, если клад поровну не делится? Ни один
пират не согласен, чтобы другому досталось золота хотя бы на грамм больше!
Инструментов, чтобы распилить или переплавить слитки, у них нет.
Подумав, пираты
решили отдать часть слитков в фонд по охране амурских тигров, чтобы оставшиеся
слитки стало возможно разделить поровну. Конечно, пираты хотят отдать золота
как можно меньше. Определите, сколько граммов золота им придётся отдать.
Входные данные
В первой строке содержится одно целое
число N (1 ≤ N ≤ 50). Во второй строке записаны через
пробел N целых чисел − веса слитков. Каждый вес лежит в
диапазоне от 1 до 1000.
Выходные данные
Выведите одно
целое число − минимальный вес слитков, которые придётся
отдать, чтобы остальные слитки можно было разделить на две равные по весу кучи.
Если клад изначально можно разделить поровну, то выведите 0.
|
Пример ввода
5
8
1 3 5 2
Пример вывода
3
|
Пояснение к примеру. Если отдать слитки с весами 1 и 2 грамма, то
оставшиеся будет несложно разделить на две равные группы по 8 граммов каждая.
Система
оценивания.
Решения, верно работающие при
N ≤ 15, будут оцениваться из 50 баллов.
