Nhà xuất bản X đang in một series truyện dài 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.

Input

• 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, \dots, a_n~ (~1 \le a_i \le 10^9, 1 \le i \le n~).

Output

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

Sample Input 1

5 3
3 7 12 8 5

Sample Output 1

13