Tatya Vicho and his blocks

5

1 votes
Problem

Tatya Vicho is very fond of playing with array of numbers. One day he was sitting idle and thinking about a problem in which he wants to find out the minimum cost to add all the blocks.

He has a number of blocks with different cost written over them. To add two blocks the cost will be the sum of the numbers written on individual blocks .After adding two blocks, these two indvidual blocks will be deleted and the resultant block will be added to the array. He will stop when there is only one block left.

Can you help him solve this problem.

 

INPUT:

Input contains an integer N i.e. length of array of blocks.

Next line contains N space separated integers denoting the cost of each block.

OUTPUT:

Print only a single line containing the minimum cost to add all the blocks.

Constraints:

1N105

1cost106

Sample Input
4
1 2 3 4
Sample Output
19
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

    

Sample Case 1:

array = [1,2,3,4]

Step1: remove(1,2) and add(1+2=3) => array = [3,3,4]

Step2: remove(3,3) and add(3+3=6) => array = [6,4]

Step3: remove(6,4) and add(6+4=10) => array = [10]

 

Cost = (1+2) + (3+3) + (6+4) = 19

Editor Image

?