Bó hoa

Có \(n\) bông hoa được đánh số từ \(1\) đến \(n\), bông hoa thứ \(i\) có độ đẹp là một số nguyên không âm \(a_i\) (với mọi \(i = 1 \ldots n\)). Tất cả \(n\) bông hoa được xếp thành một hàng ngang theo thứ tự từ \(1\) đến \(n\). Người ta cần chia \(n\) bông hoa thành \(k\) bó hoa sao cho mỗi bó hoa được ghép bởi một số bông hoa liên tiếp theo thứ tự đã xếp, mỗi bông hoa thuộc một và chỉ một bó.

Độ đẹp của một bó hoa là độ đẹp của bông hoa có giá trị nhỏ nhất trong bó hoa đó.

Yêu cầu: Tìm cách chia \(n\) bông hoa thành \(k\) bó hoa như mô tả trên sao cho tổng độ đẹp của \(k\) bó hoa là lớn nhất.

Input

Dữ liệu vào gồm:

• Dòng đầu chứa hai số nguyên dương \(n\) và \(k\) (\(1 \le k \le n \le 10^5\); \(n \cdot k \le 5 \cdot 10^6\)).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^9\) với mọi \(i = 1 \ldots n\)).

Ràng buộc:

• Có \(30\%\) số điểm có: \(k \le 2\);

• Có \(40\%\) số điểm tiếp theo có: \(n \le 500\);

• \(30\%\) số điểm còn lại không còn ràng buộc thêm.

Output

In ra là tổng độ đẹp lớn nhất của \(k\) bó hoa như yêu cầu.

Example

Input:

5 2
3 4 1 5 2

Output:

4

Note

Chia thành hai bó \((3, 4)\) và \((1, 5, 2)\) có độ đẹp lần lượt là \(3\) và \(1\), tổng bằng \(4\). Đây là tổng lớn nhất có thể.