Uolevi ja Maija ostivat divarista kasan kirjoja, ja nyt he aikovat lukea ne. Molemmat haluavat lukea kaikki ostetut kirjat. Tehtäväsi on etsiä järjestys, jossa lukemiseen kuluu yhteensä mahdollisimman vähän aikaa.

Tiedät jokaisesta kirjasta, kuinka kauan sen lukeminen vie aikaa (Uolevi ja Maija ovat yhtä nopeita lukijoita). Kirja täytyy lukea kerralla alusta loppuun, ja molemmat eivät voi lukea samaa kirjaa yhtä aikaa.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: kirjojen määrä.

Seuraavalla rivillä on n kokonaislukua a_1, a_2, \ldots, a_n: jokaisen kirjan lukemiseen kuluva aika.

Tuloste

Ohjelmasi täytyy tulostaa yksi kokonaisluku: pienin mahdollinen aika, jossa Uolevi ja Maija pystyvät lukemaan kaikki kirjat.

Rajat

• 1 \le n \le 10^5
• 1 \le a_i \le 10^9

Esimerkki

Syöte:

5
2 4 3 5 3

Tuloste:

17