Sau một chuyến phiêu lưu dài ngày, Aquarius cuối cùng cũng tìm được một kho báu cổ chứa ~n~ rương vàng được xếp thành một hàng. Rương thứ ~i~ chứa ~a_i~ đồng vàng.

Tuy nhiên, theo luật của đoàn, số rương này phải được chia thành đúng ~k~ phần liên tiếp để phân phát cho ~k~ đội viên.

Mỗi phần phải gồm một hoặc nhiều rương liên tiếp trong hàng ban đầu và mỗi rương phải thuộc về đúng một phần.

Vì muốn việc phân chia trở nên công bằng nhất có thể, Aquarius quan tâm đến phần có tổng số vàng lớn nhất. Anh muốn lựa chọn cách chia sao cho tổng số vàng của phần lớn nhất này nhỏ nhất có thể.

Hãy giúp Aquarius tìm giá trị nhỏ nhất có thể của phần có tổng số vàng lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~, lần lượt là số lượng rương vàng và số phần cần chia. ~(1 \le k \le n \le 2 \cdot 10^5)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~, trong đó ~a_i~ là số vàng trong rương thứ ~i~. ~(1 \le a_i \le 10^9)~

Output

In ra một số nguyên duy nhất — giá trị nhỏ nhất có thể của tổng lớn nhất trong ~k~ phần.

Sample Input

5 3
2 4 7 3 5

Sample Output

8

Giải thích

Ta có dãy số vàng:

2 4 7 3 5

Một cách chia tối ưu thành ~3~ phần là:

[2 4] | [7] | [3 5]

Tổng số vàng của từng phần lần lượt là:

6 | 7 | 8

Do đó phần có tổng lớn nhất chứa ~8~ đồng vàng.

Không tồn tại cách chia nào thành ~3~ phần liên tiếp mà giá trị lớn nhất nhỏ hơn ~8~.

Vì vậy đáp án là:

8