Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Kirjat

Kirjat


View task | Model solution | Statistics


Kirjat

Time limit:1.00 s
Memory limit:128 MB

Uolevi ja Maija ostivat kasan kirjoja ja 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
Esimerkki

Syöte:
5
2 4 3 5 3


Tuloste:
17