Vận chuyển

Một công ty Logictics có $K$ Drone giao hàng. Công ty nhận một đơn hàng vận chuyển $N$ thùng hàng, các thùng hàng được đánh số thứ tự từ $1$ đến $N$, thùng hàng thứ $i$ có trọng lượng là $A_i$.

Mỗi Drone tham gia sẽ vận chuyển các thùng hàng liên tiếp trong đơn hàng mà không làm thay đổi thứ tự các thùng hàng. Năng lượng vận hành của mỗi Drone được tính bằng tổng trọng lượng của các thùng hàng trên Drone. Chi phí của đơn hàng được tính bằng năng lượng vận hành lớn nhất trong các Drone tham gia vận chuyển.

Yêu cầu: Tính chi phí thấp nhất để vận chuyển đơn hàng.

Đọc từ tệp VANCHUYEN.INP gồm:

• Dòng thứ nhất chứa số nguyên dương $N$ và $K$ mỗi số cách nhau một kí tự trống ($N \ge K$).
• Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ mỗi số cách nhau một ký tự trống.

Ghi ra tệp VANCHUYEN.OUT một số nguyên duy nhất là chi phí thấp nhất để vận chuyển đơn hàng.

• Subtask 1: $20\%$ số điểm có $2 \le N \le 10$; $1 \le A_i \le 100$; $K = 2$;
• Subtask 2: $30\%$ số điểm có $10 \le N \le 100$; $1 \le A_i \le 1000$; $3 \le K \le 10$;
• Subtask 3: $50\%$ số điểm có $100 \le N \le 10^5$; $1 \le A_i \le 10^9$; $3 \le K \le 10^3$.