The greedy frog P40088


Statement
 

pdf   zip

thehtml

In a pond there are n stones 1, …, n in a row. A frog must go from stone 1 to n, in principle going consecutively through stones 2, 3, …The problem is that the frog is very greedy, and it will not help eating all the flies around each stone that it visits. To avoid fattening too much, the frog can make up to j big forward jumps, each one over at most two stones (that is, from i it can jump, at most, up to i + 3). What is the minimum number of flies that the frog will eat?

Input

Input consists of several cases. Every case begins with n and j, followed by the number of flies around each stone (n natural numbers between 0 and 104). Assume 2 ≤ n ≤ 1000, and 0 ≤ j < n.

Output

For every case, print the minimum number of flies that the frog will eat.

Public test cases
  • Input

    2 0  23 33
    2 1  23 33
    4 0  100 42 3 1000
    4 1  100 42 3 1000
    3 1  10000 10000 10000
    5 1  1000 1000 0 1000 1000
    5 2  1000 1000 0 1000 1000
    5 4  1000 1000 0 1000 1000
    

    Output

    56
    56
    1145
    1100
    20000
    3000
    2000
    2000
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++