Một hợp tác xã cần xuất khẩu ~N~ kiện hàng nông sản. Khối lượng của các kiện hàng lần lượt là ~W_1, W_2, \dots, W_N~. Hợp tác xã thuê ~K~ chiếc xe tải giống hệt nhau. Để đảm bảo quy trình kiểm kho, các kiện hàng phải được xếp lên xe theo đúng thứ tự từ ~1~ đến ~N~, không được đảo lộn thứ tự kiện hàng. Mỗi chiếc xe sẽ chở một dãy các kiện hàng liên tiếp nhau.

Yêu cầu: Tìm mức tải trọng (là sức chứa tối đa) nhỏ nhất cần thiết cho các xe tải sao cho ~K~ xe có thể chở hết ~N~ kiện hàng mà không xe nào bị quá tải.

Input

• Dòng ~1~: Hai số nguyên dương ~N~ và ~K~ ~(1 \le K \le N \le 10^5)~.

• Dòng ~2~: ~N~ số nguyên dương ~W_1, W_2, \dots, W_N~ ~(1 \le W_i \le 10^9)~.

Output

Một số nguyên duy nhất là mức tải trọng nhỏ nhất cần tìm.

Scoring

Sample Input 1

5 3
2 4 1 5 3

Sample Output 1

6

Sample Input 2

6 2
1 2 3 4 5 6

Sample Output 2

11

Notes

Với ví dụ thứ nhất, với tải trọng xe là ~6~, ta phân chia ~5~ kiện hàng cho ~3~ xe như sau:

• Xe ~1~: Chở kiện ~1~ và ~2~ (Tổng ~= 2 + 4 = 6~).

• Xe ~2~: Chở kiện ~3~ và ~4~ (Tổng ~= 1 + 5 = 6~).

• Xe ~3~: Chở kiện ~5~ (Tổng ~= 3~).

Tất cả các xe đều không chở quá ~6~. Nếu mức tải trọng là ~5~, ta sẽ cần tới ~4~ chiếc xe. Vậy ~6~ là đáp án nhỏ nhất.

Với ví dụ thứ hai, chỉ có ~2~ chiếc xe để chở ~6~ kiện hàng. Ta tìm được tải trọng tối thiểu là ~11~ với cách phân chia:

• Xe ~1~: Chở các kiện ~1, 2, 3, 4~ (Tổng ~= 1 + 2 + 3 + 4 = 10~).

• Xe ~2~: Chở các kiện ~5, 6~ (Tổng ~= 5 + 6 = 11~).

Mức tải trọng lớn nhất trong các xe là ~11~.