Bài toán: Chia mảng thành ~ k ~ đoạn con để tổng lớn nhất là nhỏ nhất

Đề bài

Cho một mảng gồm ~ n ~ số nguyên dương và một số ~ k ~. Nhiệm vụ của bạn là chia mảng thành ~ k ~ đoạn con sao cho tổng lớn nhất trong các đoạn con là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên ~ n ~ (số phần tử của mảng) và ~ k ~ (số đoạn con cần chia).
• Dòng thứ hai chứa ~ n ~ số nguyên ~ x_1, x_2, \ldots, x_n ~: các phần tử của mảng.

Output

• In ra một số nguyên: tổng lớn nhất nhỏ nhất có thể trong các đoạn con khi chia tối ưu.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq k \leq n ~
• ~ 1 \leq x_i \leq 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] ~ với tổng của các đoạn con là ~ 6, 7, 8 ~. Tổng lớn nhất là ~ 8 ~.