Cheapest Way to Merge Piles

A row of sand piles is given as piles, where piles[i] is the weight of pile i. In one move you choose exactly k piles that stand next to each other in the row and merge them into one pile, which takes their place in the row. The move costs the total weight of the piles you merged.

Write merge_cost(piles, k) that returns the smallest total cost of the moves that turn the whole row into a single pile, or -1 if that cannot be done.

Examples

merge_cost([4, 1, 3, 2], 2)     # returns 20
merge_cost([4, 1, 3, 2], 3)     # returns -1
merge_cost([2, 6, 1, 3, 5], 3)  # returns 26
merge_cost([7], 4)              # returns 0

With k = 3 every move turns 3 piles into 1, so the row loses 2 piles at a time and 4 piles can never become 1. A single pile needs no moves at all.

Constraints

• 1 <= len(piles) <= 100
• 2 <= k <= 30
• 1 <= piles[i] <= 1000