Kaaleppi aikoo rakentaa aitauksen, johon kuuluu n lautaa. Lautojen pituudet ovat a_1,a_2,\ldots,a_n.

Rakennusliike toimitti kuitenkin vain yhden pitkän laudan, jonka pituus on a_1+a_2+\ldots+a_n. Niinpä Kaalepin tulee leikata lauta osiin. Jokaisen leikkauksen kustannus on x, missä x on leikattavan laudan pituus.

Mikä on pienin mahdollinen kokonaiskustannus?

Syöte

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

Seuraavalla rivillä on n kokonaislukua a_1,a_2,\ldots,a_n: jokaisen laudan pituus.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen kokonaiskustannus.

Esimerkki

Syöte:

3
4 5 2

Tuloste:

17

Selitys: Kaaleppi jakaa ensin 11-kokoisen laudan 6- ja 5-kokoisiksi laudoiksi (kustannus 11). Sitten hän jakaa 6-kokoisen laudan 4- ja 2-kokoisiksi laudoiksi (kustannus 6). Kokonaiskustannus on 11+6=17.

Osatehtävä 1 (21 pistettä)

• 1 \le n \le 10
• 1 \le a_i \le 1000

Osatehtävä 2 (35 pistettä)

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

Osatehtävä 3 (44 pistettä)

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