Phân đoạn

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$ và số nguyên dương $k$.

Ta gọi $k$-phân đoạn của dãy số đã cho là cách chia dãy số đã cho ra thành $k$ đoạn, mỗi đoạn là một dãy con gồm các phần tử liên tiếp của dãy. Chính xác hơn, một $k$-phân đoạn được xác định bởi dãy chỉ số

$$1\le n_1<n_2<n_3<\dots <n_k=n.$$

Đoạn thứ $i$ là dãy con $a_{n_{i-1}+1},a_{n_{i-1}+2},\dots ,a_{n_i}$, $i=1,2,\dots ,k$. Ở đây quy ước $n_0=0$.

Yêu cầu: Hãy xác định số $M$ nhỏ nhất để tồn tại $k$-phân đoạn sao cho tổng các phần tử trong mỗi đoạn đều không vượt quá $M$.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1\le k\le n\le 15000$).
• Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa số nguyên $a_i$ ($|a_i|\le 30000$), $i=1,2,\dots ,n$.

Các số cạnh nhau trên một dòng cách nhau ít nhất một dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị $M$ tìm được.

Ràng buộc

• $1\le k\le n\le 15000$.
• $|a_i|\le 30000$.

Ví dụ