Cult-orcs on the stairs#4020
At the Summer Cinematic School, it's lunchtime, and the elf Kolya is eager to reach the dining hall. However, to get there, Kolya must climb a long staircase, and each step is guarded by a kultork. To pass a step, Kolya must sign up for the event organized by the kultork on that step. Each kultork hosts a unique event at a different time.
Kolya is a diligent elf and will attend any event he signs up for. However, he wants to minimize the time spent on these activities to ensure he has enough time for his cinematic studies. Fortunately, Kolya can skip some steps by jumping over them. He wants to determine the minimum time he needs to allocate for a single trip up the stairs to the dining hall.
The first line contains two integers, and (1 \leq n \leq 10000, 0 \leq k \leq 20). Here, represents the number of steps on the staircase, and is the maximum number of steps Kolya can jump over in one leap (for instance, on the first move, Kolya can jump to any step up to the (k + 1)-th). The second line contains integers, where the -th integer represents the duration in minutes of the event organized by the kultork on the -th step. No event lasts more than hours. The steps are numbered from bottom to top, with step number being the floor of the dining hall.
Output a single number: the minimum number of minutes Kolya needs to plan for his trip.
Example 1