Minimum Cost to Merge Stones

Hard

You have nums.length piles of stones arranged in a row; nums[i] is the number of stones in pile i. In one move you merge exactly k consecutive piles into a single pile, and the cost of that move equals the total number of stones in those k piles. Return the minimum total cost to merge all piles into one pile. If it is impossible, return -1.

Example 1

Input:  stones = [3,2,4,1], k = 2
Output: 20

Example 2

Input:  stones = [3,2,4,1], k = 3
Output: -1

Example 3

Input:  stones = [3,5,1,2,6], k = 3
Output: 25

Constraints

• 1 <= nums.length <= 30
• 2 <= k <= 30
• 1 <= nums[i] <= 100