Cho hai số nguyên dương ~n, k~ và dãy ~a~ có ~n~ phần tử. Xét một dãy ~b~ có ~n~ phần tử ban đầu đều bằng ~\infty~ hay ~b_i = \infty~ với ~\forall 1 \le i \le n~. Bạn được thực hiện thao tác sau vô số lần:

• Chọn cặp số nguyên ~(x, v)~ thỏa mãn ~1 \le x \le n - k + 1~, sau đó gán ~b_i = \min(b_i, v)~ với ~\forall x \le i \le x + k - 1~.

Sau một số thao tác, dãy ~b~ được gọi là đẹp nếu ~a_i \ge b_i~ với ~\forall 1 \le i \le n~.

Yêu cầu: Tính giá trị lớn nhất của tổng các phần tử dãy ~b~ sau khi dãy ~b~ trở nên đẹp.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, k~ (~1 \le k \le n \le 2000~).
• Dòng thứ hai chứa ~n~ số nguyên lần lượt là ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 100\,000~).

Output

• Ghi ra trên một dòng duy nhất là giá trị lớn nhất của tổng các phần tử dãy ~b~ sau khi dãy ~b~ trở nên đẹp.

Sample Input 1

4 2
6 6 4 2

Sample Output 1

16

Sample Input 2

5 3
3 4 4 3 1

Sample Output 2

9