Cho dãy số nguyên dương ~a_1,a_2,\dots,a_n~. Ta được phép chia dãy thành một số đoạn liên tiếp không rỗng. Với mỗi đoạn:

• Nếu độ dài đoạn nhỏ hơn ~k~ thì giá trị của đoạn bằng tổng các phần tử trong đoạn đó.

• Nếu độ dài đoạn từ ~k~ trở lên thì giá trị của đoạn bằng tổng các phần tử trong đoạn trừ đi phần tử nhỏ nhất trong đoạn.

Yêu cầu: Hãy tìm cách chia dãy số sao cho tổng giá trị của tất cả các đoạn là nhỏ nhất.

Input

• Dòng ~1~: Hai số nguyên dương ~n,k~ ~(n,k \le 10^5)~.

• Dòng ~2~: ~n~ số nguyên dương ~a_i~ ~(1 \le a_i \le 10^9; 1 \le i \le n)~.

Output

In ra một số nguyên: tổng giá trị nhỏ nhất có thể đạt được.

Scoring

Sample Input 1

5 2
2 3 1 4 6

Sample Output 1

10

Notes

Chia làm ~3~ đoạn:

~2~ ~3~ | ~1~ | ~4~ ~6~

Tổng giá trị các đoạn: ~3+1+6=10~.