135. Allocate Books (Binary Search + Greedy)

Given pages of n books (in order) and m students, allocate contiguous books so each student gets at least one book and the maximum pages assigned to any student is minimized. Return that minimum; return -1 if m>n. Input: '[books], m'.

Input: '[books], m'.

Output: Integer — minimized max pages, or -1.

Examples

Input: [12,34,67,90], 2
Output: 113
Explanation: [12,34,67] and [90].

Input: [10,20,30,40], 2
Output: 60
Explanation: [10,20,30] and [40].

Input: [1,2,3,4], 1
Output: 10
Explanation: All to one student.

Constraints

• 1<=n<=10^4
• 1<=m<=10^4
• 1<=books[i]<=10^6

Asked by