Sắp tới câu lạc bộ tin học SFIT của trường Đại Học Giao Thông Vận Tải chuẩn bị tuyển thêm thành viên. Tài là sinh viên mới vào trường rất ưa thích tin học nên rất muốn tham gia câu lạc bộ. Tuy nhiên các anh chủ nghiệm câu lạc bộ lại yêu cầu một thử thách nho nhỏ bằng một bài toán.

Cậu được cho một dãy sỏi gồm n đống, mỗi đống sỏi có ít nhất một viên sỏi. Các anh muốn Tài chia dãy sỏi này thành k đoạn liên tục sao cho tổng số sỏi lớn nhất trong các đoạn này là nhỏ nhất. Biết số viên sỏi trong một đống không bao giờ vượt quá \(10^9\).

Tuy nhiên, bỗng dưng Tài chẳng nghĩ ra được gì dù cậu rất tự tin vào khả năng của mình. Vì vậy, cậu cầu sự giúp đỡ của các bạn. Hãy giúp Tài để cậu có thể làm thành viên mới của câu lạc bộ nhé!

Đầu vào

Dòng thứ nhất chứa số tự nhiên \(n\) và \(k\) \((1 ≤ k ≤ n ≤ 10^5)\) - số đống sỏi mà Tài được đưa và số nhóm cần chia của các anh chủ nghiệm.

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((1 ≤ ai ≤ 10^9)\) - số viên sỏi trong từng đống.

Đầu ra

In ra tổng số sỏi lớn nhất trong các đoạn sau khi chia sao cho giá trị đó nhỏ nhất.

Ví dụ:

Đầu vào

10 4
1 3 2 4 10 8 4 2 5 3

Đầu ra

12

Giải thích: Ở ví dụ trên, Tài chia đoạn sỏi thành 4 đoạn (1, 3, 2, 4) (10) (8 4) (2 5 3).