Running#10152
Bessie the cow wants to become a better athlete, so she decides to run on a track for exactly minutes. During each minute, she can either run or rest for the entire minute.
The total distance Bessie can run depends on her exhaustion factor, which initially is . If Bessie runs during minute , she runs a distance of d_i, and her exhaustion factor increases by . The exhaustion factor can never exceed .
If Bessie rests, her exhaustion factor decreases by , but it cannot become negative. Bessie can resume running only when her exhaustion factor reaches . At that point, she may choose to either run or rest.
At the end of the -minute workout, Bessie's exhaustion factor must be exactly ; otherwise, she will not have enough energy left for the rest of the day.
Find the maximum total distance Bessie can run while following these rules.
The first line contains two integers n~(1 \le n \le 10^4) and m~(1 \le m \le 500).
The next lines contain the integers d_1, d_2, \ldots, d_n~(1 \le d_i \le 1000), where d_i is the distance Bessie runs if she chooses to run during minute .
Print one integer: the maximum total distance Bessie can run while satisfying all the given rules.
Example 1