Polycarp's problems
Contest: Technocup 2017 - Elimination Round 1 (Unofficially Open for Everyone, Rated for Div. 2)
Difficulty rating: 2300
Tags: binary search, dp, greedy

Polycarp is an experienced participant in Codehorses programming contests. Now he wants to become a problemsetter.

He sent to the coordinator a set of n problems. Each problem has it's quality, the quality of the i-th problem is ai (ai can be positive, negative or equal to zero). The problems are ordered by expected difficulty, but the difficulty is not related to the quality in any way. The easiest problem has index 1, the hardest problem has index n.

The coordinator's mood is equal to q now. After reading a problem, the mood changes by it's quality. It means that after the coordinator reads a problem with quality b, the value b is added to his mood. The coordinator always reads problems one by one from the easiest to the hardest, it's impossible to change the order of the problems.

If after reading some problem the coordinator's mood becomes negative, he immediately stops reading and rejects the problemset.

Polycarp wants to remove the minimum number of problems from his problemset to make the coordinator's mood non-negative at any moment of time. Polycarp is not sure about the current coordinator's mood, but he has m guesses "the current coordinator's mood q = bi".

For each of m guesses, find the minimum number of problems Polycarp needs to remove so that the coordinator's mood will always be greater or equal to 0 while he reads problems from the easiest of the remaining problems to the hardest.

Input format:
The first line of input contains two integers n and m (1 ≤ n ≤ 750, 1 ≤ m ≤ 200 000) — the number of problems in the problemset and the number of guesses about the current coordinator's mood.

The second line of input contains n integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the qualities of the problems in order of increasing difficulty.

The third line of input contains m integers b1, b2, ..., bm (0 ≤ bi ≤ 1015) — the guesses of the current coordinator's mood q.

Output format:
Print m lines, in i-th line print single integer — the answer to the problem with q = bi.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6 3
8 -5 -4 1 -7 4
0 7 3

Example output:
2
0
1

Editorial:
At first let's solve the problem for one value of Q. It is easy to show that optimal solution is the following: add to the set of tasks next task with quality equals to ai. While the value of mood (the sum of qualities and Q) is less than 0, delete from the set of remaining task the task with worst quality. The quality of such task will be less than 0, because we will not spoil the mood on previous tasks. This solution can be implement with help of structures std::set or std::priority_queue.
Described solution helps us to find answer on the query in $$O(n \log n)$$, but $${\mathcal O}(mn\log n)$$ does not fill in time limit. Note, that while we increase Q the number of deleted problems does not increase and the possible number of such numbers is only n. So we need to solve the following task: for 0 ≤ x ≤ n calculate minimum value of Q that the number of deleted problems does not exceed x. This problem can be easily solved for each x with help of binary search in $$O(n \log n \log MAXQ)$$, in sum for all x we got $${ \mathcal { O } } ( n ^ { 2 } \log n \log M A X Q )$$. Also we have an interest only m values of Q, we can make the binary search only on this values and in total we got $${ \mathcal { O } } ( n ^ { 2 } \log n \log m )$$
For each answer x with help of stored values we need to find the first answer which minimum value of Q does not more than Q in the query. We can do it easy in O(n) or with binary search in $${\mathcal {O}}(\log n)$$ (because the values Q for the answers does not increase). In total we will get O(mn) or $${\mathcal {O}}(m\log n)$$ in sum.
The best asymptotic behavior is $${\cal O}(n^{2}\log n\log m+m\log n)$$ but solutions which work in $${\cal O}(n^{2}\log n\log MAXQ+mn)$$ also passed all tests.