Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.

Separació òptima P64493

Statement

html

Donats n nombres naturals, trobeu com separar-los en dos conjunts de manera que el valor absolut de la diferència entre les sumes dels elements dels dos conjunts sigui mínima.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n seguit de n naturals entre 1 i 10⁶. Assumiu 1 ≤ n ≤ 23.

Sortida

Per a cada cas, escriviu la mínima diferència possible.

Public test cases

Input

5   18 10 19 14 3
4   1000 10 10 10
1   20
7   1 2 4 8 16 32 64

Output

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: C++ Python
User solutions: C++