Minimum Rope Concatenation Cost

MEDIUM25 pts

You are given a collection of ropes, where each rope has a positive integer length. The lengths are provided in an array called ropeLengths, where ropeLengths[i] represents the length of the i-th rope.

Your objective is to join all ropes into a single continuous rope by repeatedly tying any two ropes together. The cost of tying two ropes of lengths a and b together is equal to a + b (the sum of their lengths). After tying, the resulting rope has a length of a + b.

You must continue this process until only one rope remains. Your task is to determine the minimum total cost required to combine all ropes into one.

Key Insight: The order in which you tie the ropes together significantly affects the total cost. Choosing wisely which ropes to combine first can dramatically reduce the overall expense.

Example

Input

ropeLengths = [2, 4, 3]

Output

14

Explanation

Starting with ropeLengths = [2, 4, 3]:

Tie ropes of length 2 and 3 together for a cost of 2 + 3 = 5. Now we have [5, 4].
Tie ropes of length 5 and 4 together for a cost of 5 + 4 = 9. Now we have [9]. Only one rope remains. The total cost is 5 + 9 = 14.

Example

Input

ropeLengths = [1, 8, 3, 5]

Output

30

Explanation

Starting with ropeLengths = [1, 8, 3, 5]:

Tie ropes of length 1 and 3 together for a cost of 1 + 3 = 4. Now we have [4, 8, 5].
Tie ropes of length 4 and 5 together for a cost of 4 + 5 = 9. Now we have [9, 8].
Tie ropes of length 9 and 8 together for a cost of 9 + 8 = 17. Now we have [17]. Only one rope remains. The total cost is 4 + 9 + 17 = 30.

Example

Input

ropeLengths = [5]

Output

0

Explanation

There is only one rope, so no tying is needed. The total cost is 0.

Accepted0/0·0% Acceptance

Constraints

1 ≤ ropeLengths.length ≤ 10⁴
1 ≤ ropeLengths[i] ≤ 10⁴

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

sticks =

[2,4,3]

Minimum Rope Concatenation Cost

Hints

Minimum Rope Concatenation Cost

Hints