Bowling là một trò chơi giải trí mà người chơi ném một quả bóng nặng cho chạy trên một đường băng dài, phẳng để làm đổ những chai gỗ đứng ở cuối đường. Ngày nay, Bowling được xem là một môn thể thao. Trong bài toán này chúng ta sẽ xét trò chơi Bowling cải biên như sau:

• Cuối đường băng người ta đặt \(n\) chai gỗ được xếp thành một hàng ngang, các chai gỗ được đánh số từ \(1\) đến \(n\) từ trái qua phải. Chai gỗ thứ \(i\) ghi số nguyên \(a_i\) tương ứng là điểm thưởng (nếu \(a_i > 0\)) hoặc phạt (nếu \(a_i < 0\)) khi ném bóng mà làm đổ chai gỗ này.
• Người chơi phải ném ít nhất một lần và không giới hạn số lần ném bóng. Mỗi lần ném bóng, người chơi sẽ ném bóng hướng vào một trong \(n\) vị trí đặt chai gỗ, nếu ném bóng hướng vào vị trí đặt chai gỗ thứ \(i\) thì nó sẽ làm đổ những chai đặt ở vị trí có khoảng cách với vị trí chai thứ \(i\) không vượt quá \(k\). Khoảng cách giữa vị trí hai chai thứ \(i\) và thứ \(j\) được tính là \(|i - j|\). Tổng điểm mà người chơi đạt được là tổng các số ghi trên các chai gỗ mà người chơi làm đổ được.

Yêu cầu: Cho \(n, k\) và dãy \(a_1, a_2, \dots, a_n\), hãy tính tổng điểm lớn nhất mà người chơi có thể đạt được.

Input

• Dòng đầu ghi hai số nguyên \(n, k\);
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\), số \(a_i\) tương ứng là số ghi trên các chai gỗ thứ \(i\) (\(|a_i| \le 10^9\)).

Output

• Ghi một số nguyên là tổng điểm lớn nhất mà người chơi có thể đạt được.

Example

5 1
1 0 -10 0 1

2

5 1
1 1 1 1 1

5

5 1
-1 -1 -1 -1 -1

-2

Scoring

• Subtask \(1\): \(n \le 20, k \le n\).
• Subtask \(2\): \(n \le 2000, k \le n\).
• Subtask \(3\): \(n \le 2 * 10^5, k \le n\).

Nguồn: Thầy Đông '21