Minimum Total Division Cost

You are given an integer x and an array targetLengths of n positive integers whose sum is exactly x. You start with a single segment of length x.

On each step you choose one segment you currently have and divide it into two segments of positive integer lengths. The cost of the step is the length of the segment being divided.

You must end with exactly the segments listed in targetLengths (as a multiset; order does not matter).

Return the minimum possible total cost.

If n = 1, no divisions are needed and the cost is 0.

Examples

Example 1

Input: x = 8, targetLengths = [2, 3, 3]
Output: 13
Explanation: Divide the segment of length 8 into 5 and 3 (cost 8), then
divide the segment of length 5 into 2 and 3 (cost 5). Total cost 8 + 5 = 13.