Chia mảng

Trong một buổi họp tại văn phòng, FullHouse Dev được giao một bài toán thú vị về xử lý mảng. Họ cần phải chia một mảng thành các mảng con sao cho tổng lớn nhất trong các mảng con là nhỏ nhất có thể. Với tinh thần làm việc nhóm, FullHouse Dev bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

Bạn được cho một mảng chứa \(n\) số nguyên dương. Nhiệm vụ của bạn là chia mảng thành \(k\) mảng con sao cho tổng lớn nhất trong một mảng con là nhỏ nhất có thể.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): kích thước của mảng và số lượng mảng con trong phép chia.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): nội dung của mảng.

OUTPUT FORMAT:

• In ra một số nguyên: tổng lớn nhất trong một mảng con trong phép chia tối ưu.

Ràng buộc:

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le k \le n\)
• \(1 \le x_i \le 10^9\)

Ví dụ

INPUT

5 3
2 4 7 3 5

OUTPUT

8

Giải thích

Một cách chia tối ưu là [2,4], [7], [3,5] trong đó tổng của các mảng con lần lượt là 6, 7, 8. Tổng lớn nhất là 8 ở mảng con cuối cùng.