Zelimo da se kandidujemo za ministra prosvete. U vladi postoji n stranaka, a u i-toj a_i poslanika. Da bi stranka glasala za nas potrebno je da vise od pola poslanika iz te stranke bude za nas. Da bismo dobili na izborima potrebno je da vise od pola od ukupnog broja stranaka glasa za nas. Koliko poslanika najmanje moramo da podmitimo da bismo dobili izbore?

Ulaz:

U prvom redu standradnog ulaza nalazi se prirodan broj n ≤ 1000, broj stranaka u vladi. U narednih n redova nalazi se po jedan prirodan broj a_i - broj poslanika u i-toj stranci (a_i ≤ 10⁹).

Izlaz:

Na standardni izlaz ispisati najmanji broj poslanika koje moramo podmititi da bismo dobili izbore.

Primer:

3
6
5
6 

7

Objašnjenje.

Ukoliko podmitimo 4 poslanika iz prve i 3 poslanika iz druge stranke, ove dve stranke (od tri) će glasati za nas i mi pobedjujemo. Nije moguće pobediti tako da se podmiti manje od 7 poslanika.