671. Minimum Cost to Cut a Stick

A stick of length n has marked positions given in cuts. Each cut costs the current length of the stick being cut; performing cuts in different orders yields different total costs. 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: A single cut costs the full length.

Constraints

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

Asked by