P1353 [USACO08JAN] Running S

The cows plan to develop their athleticism through exercise. As one of them, Bessie chooses to do a morning run for $n$ minutes every day. At the beginning of each minute, Bessie chooses whether the next minute will be used for running or resting. Bessie’s stamina limits how far she can run. Specifically, if Bessie chooses to run during minute $i$, she can run $d_i$ meters in that minute, and her fatigue increases by $1$. However, at any time her fatigue must not exceed $m$. If Bessie chooses to rest, her fatigue decreases by $1$ per minute, but she must continue resting until her fatigue returns to $0$. If she rests when her fatigue is $0$, the fatigue level will not change further. At the start of the run, Bessie’s fatigue is $0$. Also, at the end of the $n$ minutes of exercise, Bessie’s fatigue must be $0$ as well, or she will not have enough energy to handle the rest of the day. Please compute the maximum total distance Bessie can run.

The first line contains two positive integers $n, m$. The next $n$ lines each contain one positive integer $d_i$.

Output a single integer, the maximum distance Bessie can run while satisfying all constraints.

Constraints For $100\%$ of the testdata, $1 \le n \le 10^4$, $1 \le d_i \le 1000$, $1 \le m \le 500$. Sample explanation: Bessie runs in minute $1$ (running $5$ meters), rests in minute $2$, runs in minute $3$ (running $4$ meters), and rests for the remaining time. Because her fatigue must be $0$ at the end of the morning run, she cannot choose to run in minute $5$. The total distance run is $9$. Translated by ChatGPT 5