Timber Cutting Order

A sawmill must cut a log of length length at every position listed in cuts (measured from the left end). Cutting a piece costs as much as the current length of that piece. After a cut, the two new pieces are cut independently. You choose the order of the cuts. Return the smallest total cost.

Examples

Input:  length = 10, cuts = [2, 4, 7]
Output: 20
Explanation: cut at 4 (cost 10), then the piece 0-4 at 2 (cost 4), then the piece 4-10 at 7 (cost 6).

Input:  length = 5, cuts = []
Output: 0

Constraints

• 2 <= length <= 10**6
• 0 <= len(cuts) <= 100; cut positions are distinct and strictly between 0 and length, in any order.
• Trying all len(cuts)! orders is hopeless; aim for O(len(cuts)**3).

Goals

• Model a sequence of operations by the first operation on an interval
• Work on the sorted cut positions instead of every unit of length