Thầy giáo có n đống sỏi, đống thứ i có a_i (i = 1, 2, …, n) viên sỏi. Thầy giáo muốn Tí chia dãy a₁, a₂, ..., a_n thành k đoạn liên tục sao cho tổng số sỏi lớn nhất trong các đoạn này là nhỏ nhất. Tuy nhiên, bỗng dưng Tí chẳng nghĩ ra được gì dù cậu rất tự tin vào khả năng của mình. Vì vậy, Tí cần sự giúp đỡ của các bạn.

Yêu cầu: Hãy giúp Tí thực hiện yêu cầu của thầy giáo.

Dữ liệu: 

          - Dòng thứ nhất chứa hai số nguyên dương n và k (k <= n <= 10⁵), là số đống sỏi và số đoạn cần chia.

          - Dòng thứ hai chứa n số nguyên dương a₁, a₂, ..., a_n (a_i <=10⁹; i = 1, 2, …, n), là số viên sỏi trong từng đống.

Hai số ghi trên cùng một dòng được phân cách nhau bởi một dấu cách.

Kết quả: Ghi ra một số nguyên là tổng số sỏi lớn nhất trong các đoạn sau khi chia sao cho giá trị đó nhỏ nhất.

Giới hạn:

- Có 50% số điểm: n <= 1000;

- Có 50% số điểm: n <= 10⁵.