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).