1191. Minimum Cost to Merge Stones

Given piles of stones in a row and an integer k, each move merges exactly k consecutive piles into one at a cost equal to the sum of those piles. Return the minimum total cost to merge all piles into one, or -1 if impossible. The input is JSON {stones, k}.

Input: JSON {stones, k}.

Output: Integer — the minimum cost, or -1.

Examples

Input: {"stones":[3,2,4,1],"k":2}
Output: 20
Explanation: Merge pairs optimally.

Input: {"stones":[3,5,1,2,6],"k":3}
Output: 25
Explanation: Two merges of three.

Input: {"stones":[3,2,4,1],"k":3}
Output: -1
Explanation: Cannot reduce to one pile.

Constraints

• 1<=n<=30
• 2<=k<=30

Asked by