Kas

Ο Kile και ο Pogi βρήκαν $N$ χαρτονομίσματα στο δρόμο. Αφού βεβαιώθηκαν ότι ο αρχικός ιδιοκτήτης δεν βρέθηκε πουθενά, αποφάσισαν να χωρίσουν τα χαρτονομίσματα μεταξύ τους. Στο τέλος θέλουν να "κερδίσουν" το ίδιο χρηματικό ποσό, οπότε μοιράζουν τα χαρτονομίσματα με τέτοιο τρόπο ώστε, το άθροισμα των χαρτονομισμάτων, με τα οποία κανείς δεν θα καταλήξει να έχει, να είναι το λιγότερο δυνατό.

Δεδομένου ότι δεν μπορούσαν απλώς να αφήσουν τα υπόλοιπα χαρτονομίσματα στο δρόμο, αποφάσισαν να πάνε σε ένα κοντινό καζίνο και να βάλουν τα πάντα στο κόκκινο, ελπίζοντας ότι θα κατέληγαν να πάρουν τα διπλάσια χρήματα που στοιχημάτισαν. Η ρουλέτα αποφάσισε τον (τυχερό, για αυτήν τη φορά) αριθμό 13 και οι ήρωές μας αποφάσισαν να μοιράσουν τα χρήματα που κέρδισαν. Η πληρωμή είναι τέτοια που ο Kile και ο Pogi θα μπορούν πάντα να χωρίζουν τα χρήματα που κέρδισαν σε δύο ίσα μέρη.

Λόγω της τεράστιας έκρηξης αδρεναλίνης, τα αγόρια έχουν χάσει τις μαθηματικές τους ικανότητες.
Βοηθήστε τους να ξεκαθαρίσουν πόσα χρήματα παίρνει ο καθένας τους στο σπίτι.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό $N(1\le N\le 500)$, που υποδηλώνει τον αριθμό των χαρτονομισμάτων στο δρόμο.
Κάθε μία από τις ακόλουθες $N$ γραμμές περιέχει έναν μόνο θετικό ακέραιο $c_i$ που υποδηλώνει την αξία του $i$-οστού χαρτονομισμάτος σε kunas (kn). Το συνολικό χρηματικό ποσό δεν θα υπερβαίνει τα $100000$ kn.

Έξοδος

Πρέπει να τυπώσετε το ποσό των χρημάτων που πήρε ο καθένας.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50 βαθμών συνολικά, $N$ θα είναι μικρότερο ή ίσο με $13$.
Σε περιπτώσεις δοκιμής αξίας 70 πόντων συνολικά, το $N$ θα είναι μικρότερο ή ίσο με $50$ και το συνολικό χρηματικό ποσό θα είναι το πολύ $1000$ kn.

Παραδείγματα

input

4
2
3
1
6

output

6

Επεξήγηση του 1ου παραδείγματος:

Ο Kile πήρε χαρτονομίσματα αξίας $2,3$ και $1kn$ και ο Pogi το χαρτονόμισμα αξίας $6kn$.

input

5
2
3
5
8
13

output

18

Επεξήγηση του 2ου παραδείγματος:

Ο Kile πήρε τα χαρτονομίσματα αξίας $5$ και $8kn$ και ο Pogi το χαρτονόμισμα αξίας $13kn$. Τα υπόλοιπα χαρτονομίσματα έχουν αξία $2$ και $3kn$, τα οποία τα αγόρια έχουν "διπλασιάσει" στο καζίνο. Τα συνολικά κέρδη καθενός από αυτά είναι $13+5=18kn$.