Dãy số

View as PDF

Submit solution


Points: 0.15 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

Cho ~1~ dãy số gồm ~N~ phần tử ~(N \leq 10000)~, mỗi phần tử có ~1~ giá trị nằm trong khoảng ~[-1000~, ~1000]~. Ban đầu, bạn sẽ ở vị trí ô số ~0~ với tổng điểm là ~0~. Mỗi nước đi, người chơi có thể di chuyển sang phải tối thiểu là ~1~ bước và tối đa là ~K~ bước ~(K \leq 10)~. Khi dừng lại ở ~1~ ô nào đó thì giá trị của ô đó sẽ được cộng vào tổng điểm. Bạn có thể dừng cuộc chơi bất cứ lúc nào. Hãy tìm cách chơi sao cho tổng điểm nhận được là nhiều nhất.

Input

  • Dòng đầu tiên chứa 2 số ~N~, ~K~.
  • Dòng thứ 2 chứa ~N~ số của dãy, mỗi số cách nhau 1 dấu cách. Mỗi số nằm trong khoảng ~[-1000, 1000]~

Output

  • Số điểm lớn nhất có thể đạt được.

Giới hạn

  • ~N \le 10000~.
  • ~K \le 10~.
  • Trong ~20\%~ số test có ~N \le 10~

Sample Input

5 2
-2 3 -6 -4 5

Sample Output

4

Note

Ta có thể đi theo thứ tự ~0 \rightarrow 2 \rightarrow 4 \rightarrow 5~. Số điểm đạt được là ~0 + 3 - 4 + 5 = 4.~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.