CSES - Omenat
  • Time limit: 1.00 s
  • Memory limit: 128 MB
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).