The emperor weighed documents on a balance and set a quota for day and night; he could not rest until it was met.
- Sima Qian, Records of the Grand Historian, ''Basic Annals of the First Emperor of Qin''
It is said that Qin Shi Huang would not rest until he had dealt with his self-imposed quota of documents. You are the court historian at his side, recording his instructions on bamboo slips. If the emperor cannot rest, neither can you.
The emperor has ordered you to bind the instructions he issued over the past days into books. Bamboo slips are strips of bamboo used for writing; several can be tied together in order to make a book. You recorded slips on day .
The emperor detests having to open several books to find one day's records. However, he does not want an excessive number of books either, so he has limited the number of completed books to at most . Since keeping him pleased is no easy task, you decide to follow a fixed rule.
The first line contains integers and , separated by a space.
The second line contains integers , separated by spaces.
Print the smallest capacity satisfying the conditions.
In the first example, with capacity , the first book contains the slips from the first and second days. The second book contains the third day's slips, and the third book contains the fourth and fifth days' slips. With a capacity smaller than , either one day's slips do not fit in a single book or more than books are needed.
In the second example, with capacity , the first book contains the slips from the first and second days, and the second book contains the third day's slips. With a capacity smaller than , no book can contain two days' slips, so the conditions cannot be satisfied.
Bind the slips in the order they were recorded, from the first day to the last. You may not split one day's slips between multiple books, but you may bind slips from different days into the same book. Do not insert blank slips to separate days.
You must choose the same positive integer capacity for every book. Each book can contain at most slips, and one day's slips must fit in a single book. You want to choose the smallest possible capacity so that the books do not become too heavy.
Initially, the first book contains no slips. If adding all of the current day's slips would bring the number of slips to at most , append them to the current book. If it would exceed , add no more slips to the current book and bind all of that day's slips into the next book. If the number becomes exactly , use the current book.
Find the smallest capacity such that binding all the slips produces at most books.
