1216. Minimum Cost to Cut a Stick

A stick of length n has cut positions given in cuts. Each cut costs the current length of the stick being cut, so the order of cuts changes the total. Return the minimum total cost to perform all cuts. The input is JSON {n, cuts}.

Input: JSON {n, cuts}.

Output: Integer — the minimum total cutting cost.

Examples

Input: {"n":7,"cuts":[1,3,4,5]}
Output: 16
Explanation: An optimal order costs 16.

Input: {"n":9,"cuts":[5,6,1,4,2]}
Output: 22
Explanation: Optimal ordering.

Input: {"n":5,"cuts":[2]}
Output: 5
Explanation: One cut costs the full length.

Constraints

• 2<=n<=10^6
• 1<=cuts<=100

Asked by