429. Binary Search on Answer — Minimum Pages

There are n books with pages[i] pages and m students. Allocate contiguous books to each student such that the maximum pages assigned to any student is minimised. Each student gets at least one book. Return -1 if m > n.

Input: Integer array pages and integer m (number of students).

Output: Minimum possible value of the maximum pages allocated.

Examples

Input: [12,34,67,90], 2
Output: 113
Explanation: Split: [12,34,67]→113, [90]→90. Max=113. Or [12,34]→46,[67,90]→157. Best split gives 113.

Input: [10,20,30,40], 2
Output: 60
Explanation: [10,20,30]→60, [40]→40. Max=60.

Input: [10,20,30], 3
Output: 30
Explanation: One book each: [10]→10,[20]→20,[30]→30. Max=30.

Constraints

• 1 <= n <= 10^4
• 1 <= pages[i] <= 10^3
• 1 <= m <= n

Asked by