EIU Programming Practices and Exams

Gần nhà Beo có một dãy rừng gỗ quý gồm n cây được đánh số từ 1 đến n và mỗi cây có một giá trị tiền nhất định. Beo sắp cưới vợ nên muốn chọn một số cây chặt để bán lấy tiền. Nhưng Beo là một người rất yêu thiên nhiên anh không muốn hủy hoại hết dãy rừng nên anh tuân thủ 2 điều kiện:

• Trong k cây liên tiếp, Beo chỉ chặt 1 cây.
• Trong dãy rừng có một số cây thuộc giống sắp tiệt chủng có giá trị k < 0 nếu chặt phải Beo sẽ bị nộp một khoản tiền cho chính quyền địa phương bằng trị tuyệt đối giá trị của cây đó.

Beo muốn có một đám cưới hoành tráng nên cần một khoản tiền càng lớn càng tốt, hãy giúp Beo chọn các cây để bán được nhiều tiền nhất.

Input

Dòng đầu tiên là số phần tử n và số nguyên k (0 < n ≤ 10⁵, 0 < k ≤ 10⁹).

Dòng tiếp theo gồm n số nguyên có giá trị tuyệt đối không quá 10⁹ - giá trị của mỗi cây.

Output

Một số nguyên duy nhất, số tiền lớn nhất mà Beo có thể nhận được.

Sample

* 80% số test case có giá trị k không quá 3.