Trong hành trình đầu tiên của chuyến du lịch vòng quanh thế giới, ledinhbaonam cùng PhuocThien, uia và Prototype quyết định ghé thăm Vịnh Hạ Long — một trong những kỳ quan thiên nhiên nổi tiếng nhất của Việt Nam.

Sau khi lên tàu tham quan, cả nhóm nhận được một bản đồ gồm \(n\) hòn đảo đá vôi được đánh số từ \(1\) đến \(n\).

Mỗi hòn đảo đều có một mức độ hấp dẫn riêng, được biểu diễn bởi một số nguyên \(a_i\).

Trong chuyến đi, đoàn tàu sẽ lần lượt đi qua các đảo theo đúng thứ tự trên bản đồ.

uia muốn chọn ra một số hòn đảo để chụp ảnh lưu niệm.

Tuy nhiên, ledinhbaonam đặt ra hai quy tắc đặc biệt:

• Không được chọn hai hòn đảo liên tiếp nhau.
• Phải chọn đúng \(m\) hòn đảo.

Mỗi hòn đảo được chọn sẽ đóng góp giá trị hấp dẫn tương ứng của nó.

Nhiệm vụ

Hãy giúp cả nhóm tìm tổng độ hấp dẫn lớn nhất có thể đạt được khi chọn đúng \(m\) hòn đảo và không có hai hòn đảo nào được chọn nằm cạnh nhau.

Input

• Dòng đầu chứa hai số nguyên \(n, m\) (\(1 \le n \le 2 \times 10^5\), \(1 \le m \le \left\lceil \frac{n}{2} \right\rceil\))

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\))

Output

• In ra tổng độ hấp dẫn lớn nhất có thể đạt được.

Example

5 2
3 7 4 6 5

13

12 4
123 456 789 321 654 987 432 765 111 999 222 888

3663