Một series truyện có ~n~ chương, chương thứ ~i~ có ~a_i~ trang. Cần chia các chương liên tiếp thành đúng ~k~ tập, mỗi chương thuộc trọn một tập và thứ tự chương được giữ nguyên.

Yêu cầu

Tìm số trang nhỏ nhất có thể của tập dày nhất sau khi chia.

Input

Dòng đầu chứa hai số ~n,k~ ~(1 \le k \le n \le 10^5)~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~.

Output

In ra số trang của tập dày nhất nhỏ nhất có thể.

Subtask

• Subtask 1: ~n \le 60~, hoặc ~k=1~, hoặc ~k=2~, hoặc ~k=n~, ~a_i \le 10^2~.
• Subtask 2: ~n<60~, ~k<4~, ~a_i \le 10^3~.
• Subtask 3: ~n \le 10^4~, ~k \le 10^3~, ~a_i \le 10^8~.
• Subtask 4: ~n \le 10^5~, ~k \le 10^4~, ~a_i \le 10^9~.

Ví dụ

5 3
3 7 12 8 5

13