#248MediumGreedy· Huffman-Style Merging with a Heap

Cable Splicing Cost

A telecom crew has several cable segments of different lengths and must splice them into one long cable. Splicing two cables of lengths `a` and `b` produces a single cable of length `a + b` and costs `a + b` units of work (the whole new length has to be wrapped and tested). Any two cables can be spliced, and the crew can choose the order freely. Return the **minimum total work** needed to turn all segments into one cable. If there is only one segment, nothing needs to be spliced and the cost is `0`.

Input format

`cables`: an array of positive integers, the segment lengths.

Output format

A single integer: the minimum total splicing cost.

Examples

Input: cables = [4, 3, 2, 6]

Output: 29

Splice 2 and 3 (cost 5), then 4 and 5 (cost 9), then 6 and 9 (cost 15): total 29, which is the minimum.

Input: cables = [1, 8, 3, 5]

Output: 30

Splice 1 and 3 (4), then 4 and 5 (9), then 8 and 9 (17): total 30.

Input: cables = [7]

Output: 0

One cable is already complete: cost 0.

Constraints

1 <= cables.length <= 10^4
1 <= cables[i] <= 10^3

#heap
#greedy
#priority-queue
#huffman