CF727F.Polycarp's problems

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 a__i (a__i 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 = b__i".

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.

Polycarp 是 Codehorses 编程竞赛的一位经验丰富的参赛者。现在他想成为一名出题人。

他向协调员提交了一组包含 $n$ 道题目的题目集。每道题目都有其质量，第 $i$ 道题的质量为 $a_i$（$a_i$ 可以为正数、负数或零）。这些题目按预期难度排序，但难度与质量之间没有任何关系：最简单的题目索引为 1，最难的题目索引为 $n$。

当前协调员的心情值为 $q$。在阅读一道题目后，其心情值会变化该题的质量值。也就是说，当协调员阅读一道质量为 $b$ 的题目后，他的心情值将增加 $b$。协调员总是从最简单到最难依次阅读题目，题目顺序不可更改。

如果在阅读某道题目后，协调员的心情值变为负数，则他会立即停止阅读，并拒绝该题目集。

Polycarp 希望从他的题目集中移除最少数量的题目，使得协调员在阅读过程中任意时刻的心情值均非负。

Polycarp 并不确定协调员当前的确切心情值，但他有 $m$ 个猜测：“当前协调员的心情值 $q = b_i$”。

对每个猜测 $b_i$，请计算 Polycarp 至少需要移除多少道题目，才能保证协调员在阅读剩余题目（仍按从最简单到最难的顺序）的过程中，心情值始终大于等于 0。

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 _a_1, _a_2, ..., a__n ( - 109 ≤ a__i ≤ 109) — the qualities of the problems in order of increasing difficulty.

The third line of input contains m integers _b_1, _b_2, ..., b__m (0 ≤ b__i ≤ 1015) — the guesses of the current coordinator's mood q.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 750$，$1 \leq m \leq 200\,000$）—— 分别表示题库中问题的数量以及对当前出题人情绪的猜测次数。

输入的第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$-10^9 \leq a_i \leq 10^9$）—— 表示按难度递增顺序排列的各问题的质量。

输入的第三行包含 $m$ 个整数 $b_1,\,b_2,\,\dots,\,b_m$（$0 \leq b_i \leq 10^{15}$）—— 表示对当前出题人情绪 $q$ 的 $m$ 次猜测。

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

输出 m 行，在第 i 行输出一个整数——即当 q = b__i 时该问题的答案。