Problem 64: Minimum Cost to Merge Stones

Problem Statement: Given an array representing piles of stones and an integer k, determine the minimum cost to merge the stones into one pile. Merging exactly k consecutive piles costs the sum of their weights. If it is impossible, output -1.

Input

The first line contains two integers n and k. The second line contains n space-separated integers representing the weight of each pile.

Output

Print the minimum cost to merge all stones into one pile, or -1 if impossible.

Examples


Input:
4 3
3 2 4 1

Output:
null

Solution Explanation

Use dynamic programming where dp[i][j] represents the minimum cost to merge stones from i to j into a certain number of piles. The transition considers merging k piles at a time. Check feasibility via (n-1) mod (k-1).

Solution in C++


#include 
#include 
#include 
#include 
using namespace std;

const long long INF = 1000000000000000000LL;

int main(){
    int n, k; 
    cin >> n >> k;
    vector stones(n);
    for(int i = 0; i < n; i++)
        cin >> stones[i];
    if((n - 1) % (k - 1) != 0){
        cout << -1 << "\n";
        return 0;
    }
    vector> dp(n, vector(n, 0));
    vector pre(n + 1, 0);
    for (int i = 0; i < n; i++)
        pre[i + 1] = pre[i] + stones[i];
    for (int len = k; len <= n; len++){
        for (int i = 0; i + len - 1 < n; i++){
            int j = i + len - 1;
            dp[i][j] = INF;
            for (int mid = i; mid < j; mid += (k - 1)){
                dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
            }
            if((len - 1) % (k - 1) == 0){
                dp[i][j] += pre[j + 1] - pre[i];
            }
        }
    }
    cout << dp[0][n - 1] << "\n";
    return 0;
}