Kile i Pogi su na ulici pronašli N novčanica. Nakon što su se uvjerili da njihov originalni vlasnik nije u blizini, odlučili su novčanice podijeliti među sobom. U konačnici žele “osvojiti” jednaku svotu novca pa su tako i podijelili novčanice. Naravno, suma vrijednosti novčanica koje nisu pripale nikome bila je najmanja moguća.

Budući da nisu mogli preostale novčanice samo tako ostaviti na ulici, odlučili su posjetiti obližnji casino i staviti sve na crveno ​u nadi da će dobiti duplo više novca nego što su uložili. Na ruletu se okrenuo (ovaj puta sretni) broj \(13\) i naši junaci su među sobom podijelili osvojen novac. Način isplate je takav da će Kile i Pogi uvijek moći podijeliti osvojeni novac na dva jednaka dijela.

Zbog silnog adrenalina, momci su izgubili svoje matematičke sposobnosti. Pomozite im odgonetnuti koliku je svotu novca svaki od njih ponio kući.

Ulazni podaci

U prvom redu nalazi se prirodni broj \(N\) \((1 \leq N \leq 500)\) koji označava broj novčanica koje se nalaze na ulici.

U sljedećih \(N\) redaka nalazi se po jedan prirodan broj ci koji označava kunsku vrijednost \(i\)-te novčanice. Ukupna svota novca bit će najviše \(100 000\) kn.

Izlazni podaci

Ispišite koliko je novca svaki od momaka ponio kući.

Bodovanje

U test podacima ukupno vrijednima \(50\) bodova \(N\) će biti manji ili jednak \(13\).

U test podacima ukupno vrijednima \(70\) bodova \(N\) će biti manji ili jednak \(50\), a ukupna svota novca iz ulaza bit će najviše \(1000\) kn.

Primjeri test podataka

Ulaz

4
2
3
1
6

Izlaz

6

Objašnjenje

Kile je uzeo novčanice od \(2\), \(3\) i \(1\) kn, a Pogi je uzeo novčanicu od \(6\) kn.

Ulaz

5
2
3
5
8
13

Izlaz

18

Objašnjenje

Kile je uzeo novčanice od \(5\) i \(8\) kn, a Pogi je uzeo novčanicu od \(13\) kn. Ostale su novčanice od \(2\) i \(3\) kn koje su momci “poduplali” u casinu. Ukupna zarada svakog od njih je \(13 + 5 = 18\) kn.