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$