Nhân dịp chào mừng ngày thành lập Đoàn TNCS Hồ Chí Minh, Đoàn trường tổ chức vẽ một bức tranh khổng lồ trên tường rào. Bức tường được chia sẵn thành ~n~ phần liên tiếp nhau. Do độ khó khác nhau, phần tường thứ ~i~ cần thời gian là ~a_i~ phút để vẽ xong. Có ~K~ nhóm học sinh câu lạc bộ mỹ thuật được giao nhiệm vụ hoàn thiện bức tranh này.

Để hoàn thành bức tranh, thầy Bí thư Đoàn trường quyết định chia ~n~ phần tường này thành đúng ~K~ đoạn liên tiếp nhau (mỗi nhóm phụ trách vẽ một đoạn, mỗi đoạn có thể gồm nhiều phần liên tiếp). Thời gian vẽ xong một đoạn là tổng thời gian vẽ các phần trong đoạn đó. Thời gian để hoàn thành bức tranh bằng thời gian vẽ của đoạn lâu nhất trong một cách chia.

Yêu cầu: Bạn hãy giúp thầy Bí thư Đoàn trường tìm thời gian hoàn thành bức tranh nhanh nhất.

Ví dụ: Cho bức tường có ~n = 4~, thời gian lần lượt vẽ các phần là: ~1, 2, 3~ và ~4~ phút. Với ~K = 3~ thì có các cách chia như sau:

• Cách 1: ~(1), (2), (3, 4)~: Thời gian hoàn thành bức tranh là ~7~ phút;

• Cách 2: ~(1), (2, 3), (4)~: Thời gian hoàn thành bức tranh là ~5~ phút;

• Cách 3: ~(1, 2), (3), (4)~: Thời gian hoàn thành bức tranh là ~4~ phút.

Vậy thời gian hoàn thành bức tranh nhanh nhất là ~4~ phút.

Input

• Dòng 1: Chứa hai số nguyên dương ~n~ và ~K~.

• Dòng 2: Chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^9)~. Các số cách nhau ít nhất một dấu cách.

Output

• Một số nguyên duy nhất thoả mãn yêu cầu của bài toán.

Scoring

Sample Input 1

4 3
1 2 3 4

Sample Output 1

4