Book Allocation Problem

You are given n books with a certain number of pages, and k students. Your task is to assign books to students in a contiguous manner such that the maximum number of pages assigned to a student is minimized.

Problem Details:

• Each book must be allocated to exactly one student.
• Books are arranged in a fixed order and each student gets a contiguous segment.
• The goal is to minimize the maximum pages any student has to read.

This problem can be solved efficiently using binary search. Mathematically, if we denote by \( f(x) \) a predicate that returns true if the books can be divided among k students such that no student reads more than \( x \) pages, then the solution is to find the minimum \( x \) satisfying \( f(x) = \text{true} \). The search range is from \( \max(\text{pages}) \) to \( \sum_{i=1}^{n} \text{pages}_i \).

inputFormat

The first line contains two integers n and k, representing the number of books and the number of students, respectively. The second line contains n space-separated integers, where the i-th integer represents the number of pages in the i-th book.

outputFormat

Output a single integer: the minimum possible maximum number of pages assigned to a student.## sample

4 2
12 34 67 90

113