Задача E. Две кучки

Автор:М. Спорышев   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Однажды у Хана Соло и Леи Скайуокер родились двое детей. Когда детям было около года они любили играть с камушками. Тогда Лея и Хан решили собрать им по кучке красивых камней. К обеду они насобирали камней, но надо было распределить их на две кучки так, чтобы дети не поссорились. Для этого камни надо распределить так, чтобы разница между суммарными весами двух кучек была минимальной и надеяться, что дети ее не заметят.

Формат входного файла

В выходном файле содержится целое число N - количество камней. Следующие N чисел Wi - веса каждого камня.

Формат выходного файла

Выходной файл должен содержать единственное неотрицательное целое число C - минимальная разность весов.

Ограничения

1 ≤ N ≤ 20 1 ≤ Wi ≤ 100000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
0

0.020s 0.006s 15