Reiz sensenos laikos augstu kalnos dzīvoja apiņu audzētājs Ceks. Cekam bija divi dēli - Ricibuks un Cibiruks. Ar apiņu audzēšanu Ceks bija iepelnījis diezgan lielu kaudzi nacionālās naudas - fūgrikus. Fūgrikiem īpatnēji ir tas, ka viņi pieejami ar visvisādiem nomināliem, no 1 līdz pat 32000. Bija pagājis zināms laiks, dēli bija pieauguši un gribēja doties plašajā pasaulē jaunos apiņu stādus meklēt. Taču pirms došanās pasaulē, viņi nolēma, ka jāiet sencim nauda paprasīt. Ceks žēli nopūtās un saprata - kas jādod, jādod. Taču labāk atdot pēc iespējas mazāk. Viņš saprata arī to, ka abiem dēliem jāatdod vienādas naudas summas, citādi, ja iedosi Ricibukam vairāk, Cibiruks apvainosies un otrādi.

Cekam ir maiss ar naudu, kurā ir N dažādas naudas zīmes ar nomināliem A₁, A₂, A₃ ... līdz A_N, pie kam vairākām naudas zīmēm vērtības var būt vienādas. Jūsu uzdevums ir uzrakstīt programmu, kas palīdz Cekam izrēķināt kāds ir tas mazākais daudzums naudas, no kura viņam jāšķiras, lai abiem dēliem tiktu vienāda naudas summa.

Ievaddatu pirmajā rindā atrodas viens skaitlis N ( 2 <= N <= 100 ), kas apzīmē naudaszīmju daudzumu maisā. Katra nākamā rinda satur vienu skaitli A_i, kas ir i-tās naudas zīmes vērtība ( 1 <= A_i <= 32000 ).

Izvaddatu vienīgā rinda satur atbildi - mazāko naudas daudzumu, no kura Ceks var šķirties, tā, lai katram dēlam tiek vienāda naudas summa. Garantēts, ka atrisinājums vienmēr eksistē un ka summa, no kuras Cekam ir jāšķiras, ir mazāka par 100000.

Testpiemērā viens dēls dabū naudas zīmes 1,2,5, otrs - naudas zīmi ar vērtību 8. Abi ir dabūjuši vienādu naudas summu - 8 fūgrikus un tā ir mazākā iespējamā naudas summa, no kuras nāksies škirties papucim.

Autors: Ģirts Folkmanis