Maahan on pudonnut $n$ omenaa, ja tiedät jokaisen omenan painon. Tehtäväsi on jakaa omenat Uoleville ja Maijalle niin, että heidän saamiensa omenoiden yhteispainot ovat mahdollisimman lähellä toisiaan.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: omenoiden määrä.

Seuraavalla rivillä on $n$ kokonaislukua $p_1,p_2,\ldots,p_n$: omenoiden painot.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: yhteispainojen ero.

Rajat

• $1 \le n \le 20$
• $1 \le p_i \le 10^9$

Esimerkki

Syöte:

5
3 2 7 4 1

Tuloste:

1

Selitys: Yksi ratkaisu on, että Uolevi saa omenat 3, 2 ja 4 (yhteispaino 9), ja Maija saa omenat 7 ja 1 (yhteispaino 8).