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~.

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 100000)~.

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.

Scoring

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