Chia hành lý

nguồn : https://cses.fi/problemset/task/1085/

Sau khi Đồ đệ lớn nhất của Sugar Tank- Tôn Ngộ Không bị đánh bại bởi Công-kun, Trư Bát Giới lên nắm quyền và quyết định chia hành lý để ai về nhà nấy.

Khổ nỗi, não của Trư Bát Giới cũng như ví của sinh viên cuối tháng - không có gì. Bạn hãy giúp Trư Bát Giới chia hành lí nhé. Biết rằng có ~n~ vật phẩm, mỗi vật phẩm có giá trị là ~a_i~ và phải chia cho ~k~ đồ đệ. Nhưng để đơn giản hóa việc chia hàng, Trư Bát Giới sẽ chọn các món hành lí liên tiếp nhau, sao cho giá trị tổng lớn nhất trong ~k~ đống hành lí đó là nhỏ nhất có thể. Tính giá trị trên.

Input

Dòng đầu tiên chứa ~n~ và ~k~ ~(1 \leq k \leq n \leq 10^5)~

Dòng tiếp theo chứa ~n~ số ~a_i~, giá trị từng món hành lý. ~(1 \leq a_i \leq 10^9)~

Output

1 dòng duy nhất, giá trị tổng lớn nhất trong ~k~ đống hành lí đó là nhỏ nhất có thể.

Sample Input

5 3
2 4 7 3 5

Sample Output

8

Giải thích

cách chọn tốt nhất là ~[2,4],[7],[3,5]~ các giá trị tổng lần lượt là ~6,7,8~. Đây chính là cách chọn tốt nhất có thể