Dưa hấu

Có $N$ quả dưa hấu trên một băng chuyền, quả thứ $i$ có thể tích là $A_i$. Băng chuyền lần lượt đẩy các quả dưa từ quả thứ $1$ đến quả thứ $N$ xuống các thùng.

Ngay dưới băng chuyền có $K$ thùng xếp theo thứ tự, mỗi thùng có cùng sức chứa $X$. Băng chuyền bắt đầu đẩy dưa xuống thùng thứ nhất. Nếu thùng hiện tại không thể chứa thêm quả dưa sắp được đẩy xuống (tức là tổng thể tích các quả dưa trong thùng cộng thêm thể tích quả dưa đó vượt quá $X$) thì băng chuyền tự động chuyển sang thùng tiếp theo. Các thùng không nhất thiết phải được dùng hết.

Vì không muốn lãng phí, hãy tìm sức chứa $X$ nhỏ nhất sao cho với $K$ thùng sức chứa $X$ có thể chứa được tất cả $N$ quả dưa hấu.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên $N,K$ ($1\le N,K\le {10}^5$).
• Dòng tiếp theo gồm $N$ số nguyên $A_1,A_2,\dots ,A_N$ ($1\le A_i\le {10}^9$).

Dữ liệu ra

In ra giá trị $X$ nhỏ nhất sao cho có thể chứa tất cả $N$ quả dưa trong $K$ thùng.

Ràng buộc

• $1\le N,K\le {10}^5$ ($K$ có thể lớn hơn $N$).
• $1\le A_i\le {10}^9$.
• $25\%$ số test có $N,K\le 100$.
• $25\%$ số test khác có $N,K\le 1000$.

Ví dụ