A foundry lines up n slag piles in a row, each with a positive integer weight. In one move you take exactly k consecutive piles and merge them into a single pile whose weight is the sum of those k piles; the move costs that summed weight. You repeat until a single pile remains.
Depending on n and k, reducing the whole row to one pile may be impossible. If it is impossible, report -1. Otherwise report the minimum total cost.
Input format
Line 1: two integers n and k, the number of piles and the merge width.
Line 2: n space-separated positive integers, the pile weights from left to right.
Output format
A single integer: the minimum total merge cost, or -1 if the row cannot be reduced to one pile.
Constraints
- 1 <= n <= 200
- 2 <= k <= n (when n >= 2); when n is 1 the answer is 0 and any k >= 2 may appear.
- 1 <= each weight <= 1000