Разделить поровну

Даны веса $n$ предметов. Разложите все предметы на две кучи так, чтобы разность суммарных весов была наименьшей.

Знакомая задача, но веса до $10^{12}$: рюкзак по суммам не построишь. Зато $n \le 36$ — значит встреча посередине.

В первой строке $n$ ($1 \le n \le 36$). Во второй — $n$ чисел $w_i$ ($1 \le w_i \le 10^{12}$).

Выведите наименьшую возможную разность сумм.