<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

183. Painting the balls
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



Petya puts the N white balls in a line and now he wants to paint some of them in black, so that at least two black balls could be found among any M successive balls. Petya knows that he needs Ci milliliters of dye exactly to paint the i-th ball. Your task is to find out for Petya the minimum amount of dye he will need to paint the balls.

Input
The first line contains two integer numbers N and M (2<=N<=10000, 2<=M<=100, M<=N). The second line contains N integer numbers C1, C2, ..., CN (1<=Ci<=10000).

Output
Output only one integer number - the minimum amount of dye Petya will need (in milliliters).

Sample test(s)

Input
6 3
1 5 6 2 1 3

Output
9

Note
Example note: 1, 2, 4, 5 balls must be painted.
Author:	Andrew V. Lazarev
Resource:	ACM International Collegiate Programming Contest 2003-2004
North-Eastern European Region, Southern Subregion
Date:	2003 October, 9

<|response|>
1. Abridged problem statement  
We have N white balls in a row, each ball i can be painted black at cost Ci. We must paint enough balls so that in every contiguous block of M balls there are at least two black balls. Compute the minimum total cost.

2. Key observations  
- If you look at any two consecutive painted balls, say at positions p and q, then to guarantee two blacks in every M-segment, the gap (q–p) between adjacent painted balls must be ≤ M.  
- We also need the run before the first painted ball and the run after the last painted ball to be small enough that the first and last windows each contain two blacks. This is naturally handled by imagining a virtual painted ball just before position 0 and one just past the end.  
- A dynamic programming on the last painted ball index and the gap back to the previous painted ball captures the needed "two-per-M" constraint locally.

3. Full solution approach  
Define dp[i][d] = minimum cost to paint ball i black (0-based) with the distance back to the previous painted ball equal to d (1 ≤ d ≤ M).  
- We only allow 1 ≤ d ≤ M, because if d > M, some M-segment between those two painted balls would contain at most one black.  
- Initialization (first painted ball): imagine a virtual painted ball at position −1. If ball i is painted first, its gap to the virtual one is d = i+1. To ensure the first actual window of length M sees two blacks, we need i+1 < M, i.e. i < M−1; for such i set dp[i][i+1] = Ci.  
- Transition: from a state (i, prv_dist), we can paint a new ball nxt = i + dist (1 ≤ dist ≤ M). We require prv_dist + dist ≤ M, so that any window spanning the two painted balls at i and nxt still has at least two blacks. Then update dp[nxt][dist] = min(dp[nxt][dist], dp[i][prv_dist] + C[nxt]).  
- Answer: among all states (i, d) such that the tail gap (N − i) + d ≤ M, take the minimum dp[i][d]. That ensures the trailing segment also has two blacks.  
- Complexity: there are O(N·M) states, and each state considers up to M transitions, so O(N·M²). With M ≤ 100 and N ≤ 10000 this is acceptable in optimized C++.

4. C++ implementation  
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<int> a;

void read() {
    cin >> n >> m;
    a.resize(n);
    cin >> a;
}

void solve() {
    // We must paint balls so every window of M consecutive balls holds at
    // least two black ones; this is equivalent to forcing the gap between any
    // two consecutive black balls to be at most M (and the same on both ends).
    // dp[i][d] = minimum cost to paint ball i black given that the previous
    // black ball is exactly d positions earlier (d in 1..M). Transitions move
    // to the next black ball nxt = i + dist with the constraint prv_dist +
    // dist <= M (so the two windows straddling ball i still contain two black
    // balls). A state is a valid finishing state when the remaining tail
    // n - i together with prv_dist still fits within M, and the answer is the
    // minimum such dp value.

    vector<vector<int>> dp(n, vector<int>(m + 1, (int)1e9));
    for(int i = 0; i < m - 1; i++) {
        dp[i][i + 1] = a[i];
    }

    int ans = (int)1e9;
    for(int i = 0; i < n; i++) {
        for(int prv_dist = 1; prv_dist <= m; prv_dist++) {
            for(int dist = 1; dist <= m; dist++) {
                int nxt = i + dist;
                if(nxt < n && prv_dist + dist <= m) {
                    dp[nxt][dist] =
                        min(dp[nxt][dist], dp[i][prv_dist] + a[nxt]);
                }
            }

            int left_to_end = n - i;
            if(prv_dist + left_to_end <= m) {
                ans = min(ans, dp[i][prv_dist]);
            }
        }
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys
input = sys.stdin.readline
INF = 10**18

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))  # 0-based

    # dp[i][d]: minimum cost if ball i is painted, and previous painted was at i-d (1 <= d <= m)
    dp = [ [INF]*(m+1) for _ in range(n) ]

    # Initialize first painted ball at index i, gap = i+1 to virtual -1; require i+1 < m
    for i in range(n):
        if i + 1 < m:
            dp[i][i+1] = a[i]
        else:
            break

    answer = INF

    for i in range(n):
        # Check if we can end here; tail gap = n-i
        for d in range(1, m+1):
            cost = dp[i][d]
            if cost >= INF:
                continue
            # ensure trailing segment has two blacks: d + (n - i) <= m
            if d + (n - i) <= m:
                answer = min(answer, cost)

        # Transition: from (i, d1) paint next at j = i+dist
        for d1 in range(1, m+1):
            base = dp[i][d1]
            if base >= INF:
                continue
            # dist must satisfy d1 + dist <= m
            for dist in range(1, m - d1 + 1):
                j = i + dist
                if j >= n:
                    break
                new_cost = base + a[j]
                if new_cost < dp[j][dist]:
                    dp[j][dist] = new_cost

    print(answer)

if __name__ == "__main__":
    main()
```
