Problema Nea Ghita

Nea Ghiță tocmai a ieșit la pensie și pentru a putea să își ocupe timpul liber, și-a creat de curând un cont pe o rețea de socializare populară. Deja a fost adăugat în n grupuri cu prieteni, foști colegi și alte persoane pe care le cunoaște. Fiecare grup i (1 ≤ i ≤ n) are ai membri.

Epuizat de numărul de mesaje și postări care se trimit sau distribuie necontenit, Nea Ghiță decide într-o zi să iasă din câteva grupuri. Dorința lui ar fi ca numărul de persoane din grupurile în care să rămână membru să fie cât mai apropiat de numărul de persoane din grupurile din care iese.

Fiind fost profesor de informatică, Nea Ghiță decide să îți propună chiar ție să creezi un program care, având numărul de persoane din fiecare grup în parte, să afișeze diferența minimă de persoane care se obține dacă acesta iese dintr-un număr de grupuri, exact cum a descris el mai sus.

Cerință

Se dau n și n numere reprezentând numărul de persoane din fiecare dintre cele n grupuri. Să se determine diferența minimă de persoane dacă acesta iese din câteva dintre grupuri.

Date de intrare

Fișierul de intrare ghita.in conține pe prima linie numărul natural n. Pe a doua linie se află n numere naturale separate prin câte un spațiu, reprezentând numărul de persoane din fiecare grup în parte.

Date de ieșire

Fișierul de ieșire ghita.out conține un singur număr, reprezentând diferența minimă în valoare absolută care se poate obține dintre persoanele din grupurile în care rămâne și persoanele din grupurile din care iese, dacă acesta iese optim.

Restricții și precizări

• 1 ≤ n ≤ 15
• 1 ≤ numărul de persoane dintr-un grup ≤ 1.000.000.000 (Nea Ghiță are foarte mulți prieteni)
• Considerăm că persoanele din toate grupurile sunt distincte

Exemple