Nhà xuất bản X đang in một seri truyện dài kỳ gồm ~n~ chương, chương thứ ~i~ có ~a_i~ trang (~1 \le i \le n~). Ban biên tập quyết định in thành ~k~ tập, sao cho mỗi chương phải nằm gọn trong một tập, tập 1 bao gồm một hoặc một số chương đầu tiên, mỗi tập tiếp theo bao gồm một hoặc một số chương tiếp theo. Thứ tự các chương xuất hiện từ tập 1 đến tập thứ ~k~ đảm bảo là các chương liên tiếp từ chương thứ 1 đến chương thứ ~n~.

Ban biên tập có nhiệm vụ phân chia ~n~ chương thành ~k~ tập sao cho số trang của tập dày nhất là ít nhất.

Yêu cầu: hãy xác định số trang của tập dày nhất nhận được sau kết quả làm việc của ban biên tập.

Dữ liệu

Từ bàn phím gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 10^5~);
• Dòng thứ 2 chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~, ~1 \le i \le n~).

Kết quả

In ra màn hình số trang của tập dày nhất.

Ví dụ

Dữ liệu vào

5 3
3 7 12 8 5

Dữ liệu ra

13

Giải thích: Với ~n = 5~, số trang trong mỗi chương tương ứng lần lượt là: 3, 7, 12, 8, 5 và chia thành 3 tập thì tập 1 sẽ chứa chương 1 và 2 với tổng số trang là 10, tập 2 chứa chương 3 với tổng số trang là 12, tập 3 chứa hai chương cuối với tổng số trang là 13. Cách chia này phù hợp với yêu cầu đã nêu, đảm bảo tập dày nhất có số trang ít nhất là 13.

Giới hạn

• Subtask 1 (20% số điểm): ~n \le 60~; ~k = 1~ hoặc ~k = 2~ hoặc ~k = n~, ~a_i \le 10^2~;
• Subtask 2 (30% số điểm): ~n < 60~; ~k < 4~, ~a_i \le 10^3~;
• Subtask 3 (40% số điểm): ~n = 10^4~; ~k = 10^3~; ~a_i \le 10^8~;
• Subtask 4 (10% số điểm): ~n = 10^5~; ~k \approx 10^4~; ~a_i \le 10^9~.