Dãy số


Submit solution

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

Problem type

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

There are no comments at the moment.