Đề bài

Cho dãy \(N\) số nguyên dương và số nguyên \(K\). 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 giá trị lớn nhất trong các tổng đoạn là nhỏ nhất. In ra giá trị nhỏ nhất đó

Dữ liệu vào

\(N, K (1 \le N \le 2*10^5)\) \(N\) số nguyên \(a_i (1 \le a_i \le 10^9)\)

Dữ liệu ra

Một số nguyên: giá trị nhỏ nhất có thể của tổng lớn nhất trong các đoạn.

Ví dụ