Մալուխների միացում
Տրված է n մալուխ, որոնց երկարությունները հայտնի են: Ուզում եք դրանք միմյանց միացնել, որպեսզի ստացվի մեկ շարունակական, երկար մալուխ։ Երկու մալուխ (x և y երկարություններով) միացնելիս դուք պետք է վճարեք x + y գումար: Միացնելուց հետո նոր առաջացած մալուխի երկարությունը կլինի x + y:
Ո՞րն է այն նվազագույն գումարը, որը դուք կծախսեք բոլոր մալուխները միացնելու համար:
Մուտք
Մուտքի առաջին տողում տրված է n ամբողջ թիվը (1 ≤ n ≤ ), որը մալուխների քանակն է:
Հաջորդ տողում տրված են բացատներով բաժանված (1 ≤ ≤ ) արժեքները, որոնք համապատասխան մալուխների երկարություններն են:
Ելք
Ծրագիրը պետք է տպի այն նվազագույն գումարը, որը կծախսվի բոլոր մալուխները միացնելու համար:
Օրինակներ
Մուտք | Ելք |
|---|---|
5 1 2 3 6 2 | 30 |
Բացատրություն
Միացնում ենք 1-ը և 2-ը ⇒ վճարում ենք 3 ⇒ 3 3 6 2
Միացնում ենք 2-ը և 3-ը ⇒ վճարում ենք 5 ⇒ 5 3 6
Միացնում ենք 3-ը և 5-ը ⇒ վճարում ենք 8 ⇒ 6 8
Միացնում ենք 6-ը և 8-ը ⇒ վճարում ենք 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB