Cho một dãy ~A~ gồm ~n~ phần tử, hãy tìm số nguyên ~x~ nhỏ nhất sao cho dãy ~A~ có thể được chia thành đúng ~k~ đoạn con liên tiếp, mỗi đoạn có tổng không vượt quá ~x~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \ldots, A_n~.

Kết quả

In ra số nguyên ~x~ là đáp án.

Ví dụ

Đầu vào:

5 2
5 4 3 2 1

Đầu ra:

9

Giải thích: Một cách chia hợp lệ là ~[5, 4]~ và ~[3, 2, 1]~ với tổng lần lượt là ~9~ và ~6~. Không có cách chia nào nếu ~x~ nhỏ hơn ~9~.

Giới hạn

• ~1 \le k \le n \le 10^5~
• ~1 \le A_i \le 10^9~

Mỗi đoạn phải chứa ít nhất một phần tử. Đáp án luôn nằm trong đoạn từ ~\max A_i~ đến tổng của cả dãy, và tổng này có thể lên tới ~10^{14}~.