Minimum Daily Pages

In this problem, a student needs to finish reading n books within m days. Each book has a given number of pages. The student must read the books in order and cannot split a book into parts. Your goal is to determine the minimum number of pages that the student must read per day so that all books can be finished within m days.

Formally, given an integer $n$ (the number of books), an integer $m$ (the number of days), and an array of integers $pages = [p_1, p_2, \dots, p_n]$, find the smallest integer $X$ such that the books can be partitioned into at most $m$ contiguous segments and the sum of pages in each segment does not exceed $X$.

Input Constraints:

• $1 \leq n \leq 10^5$
• $1 \leq m \leq n$
• $1 \leq p_i \leq 10^9$

A binary search based solution along with a greedy checking strategy is sufficient to solve this problem efficiently.

inputFormat

The first line contains two integers n and m, representing the number of books and the number of days respectively. The second line contains n space-separated integers representing the number of pages in each book.

outputFormat

Output a single integer, which is the minimum number of pages that must be read per day to finish all the books within m days.## sample

5 5
100 200 300 400 500

500