Một công ty thiết kế xây dựng đang lưu trữ các file bản vẽ lớn. Họ cho dãy A gồm N số nguyên dương, mỗi phần tử là một số biểu diễn dung lượng của một file bản vẽ. Hãy chia dãy thành đúng K đoạn liên tiếp (mỗi đoạn không rỗng) sao cho:

• Mỗi đoạn chứa các phần tử (file) liên tiếp.
• Giá trị lớn nhất của tổng các phần tử (file) trong mỗi đoạn là nhỏ nhất có thể.

Yêu cầu: Tìm giá trị nhỏ nhất của tổng lớn nhất trong các đoạn sau khi chia.

Dữ liệu vào:

• Dòng 1: Cho hai số nguyên N, K (1 ≤ K ≤ N ≤ 105)
• Dòng 2: N số nguyên Ai (1 ≤ Ai ≤ 109)

Dữ liệu ra: In ra một số nguyên là kết quả theo yêu cầu của đề bài.

Ví dụ:

Input:

5 2

7 2 5 10 8

Output:

18

Giải thích: Chia: [7 2 5] và [10 8]; Max = 14 vs 18 → chọn 18 là nhỏ nhất có thể.