Fence Repair

Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs $N$ ($1 \le N \le 20{,}000$) planks of wood, each having some integer length $L_i$ ($1 \le L_i \le 50{,}000$) units. He then purchases a single long board just long enough to saw into the $N$ planks, that is, a board whose length is the sum of the lengths $L_i$. He ignores the "kerf", the extra length lost to sawdust when a cut is made, and so should you.

Farmer John does not own a saw, so he takes the long board to Farmer Don's farm and politely asks to borrow one. Farmer Don refuses to lend a saw and instead offers to charge Farmer John for each of the $N-1$ cuts. The charge to make one cut is exactly equal to the length of the piece being cut; for example, cutting a piece of length 21 costs 21 cents.

Making $N$ planks requires $N-1$ cuts in total. Farmer John may choose the order and positions of the cuts, and because different orders produce intermediate pieces of different lengths, the total charge varies. Determine the minimum amount of money Farmer John must spend to create the $N$ planks.

• Line 1: One integer $N$, the number of planks.
• Lines 2..N+1: Each line contains a single integer, the length of one needed plank.

• Line 1: One integer, the minimum amount of money needed to make the $N-1$ cuts.

The original board measures $8+5+8=21$. The first cut costs 21 and splits the board into pieces of length 13 and 8. The second cut costs 13 and splits the 13 into 8 and 5, for a total of $21+13=34$. If the 21 had instead been cut into 16 and 5, the second cut would cost 16, for a total of 37, which is more than 34.