class Solution {
public:
    int calculateCost(vector<int> arr, int threshold) {
        int n = arr.size();
        vector<int> dp(n + 1);
        for (int i = 1 ; i <= n ; i++) {
            int curMin = 0, best = 0;
            for (int j = 1 ; j <= threshold && i - j >= 0 ; j++) {
                curMin = min(curMin, arr[i - j]);
                best = min(best, dp[i - j] + curMin * j);
            }
            dp[i] = best; 
        }
        return dp[n];
    }
};