A novel in k days

binary search greedy classic interviews

A book consists of n chapters, and the length of each in words is known. It must be read in order and in whole chapters, and finished in k days (sooner is fine too). What is the smallest daily limit of words that allows this? Each k in a list needs its own answer.

The second and third tests are the 361 chapters of “War and Peace” in the Russian original. To finish in a month you have to read at most 15,802 words a day, and if you stretch it over a year, the limit runs into the longest chapter.

Input

The first line holds n and q (1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10). The second holds the chapter lengths, integers from 1 to 10⁶. The third holds q numbers k (1 ≤ k ≤ 10⁹).

Output

For each k, the smallest daily limit.

Examples

Example 1

Input

6 4
5 2 7 3 4 6
1 2 3 6

Output

Limits

Time · Python: 7000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

If a limit L lets you finish in k days, any limit greater than L does too. And a particular limit is easy to check: each day read as many chapters as fit.

2The idea

The answer is the first L for which “the days needed are at most k”. The function “how many days are needed with limit L” does not increase as L grows, so the boundary is found by binary search over L, and each candidate is checked greedily in one pass.

3Walkthrough

The search range: from below, the longest chapter (it cannot be less: that chapter cannot be split); from above, the sum of all chapters (the whole book in a day). The greedy check is right: putting a chapter into the current day while it fits always pays off, because any plan can be adjusted so that earlier days are filled no less, and that adds no days.

The sum reaches 10¹¹, so Go needs an int64.

3+Solution

4Complexity

A range of up to 10¹¹ takes about 37 checks, each O(n): O(n log S) per k, where S is the sum of the lengths.

5Common mistakes

Trying limits one after another. From the longest chapter to the answer can be more than a million steps, each a pass over the chapters.
A lower bound of zero. A limit below the longest chapter does not work for any k, but the greedy check will not notice: it opens a day with a chapter that does not fit into it, and the search returns a limit smaller than the longest chapter.
“Exactly k days”. If fewer days are enough, that fits too: the statement says “at most k”.

Algorithms behind it

SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems