← 返回题目列表

Codeforces · 727/F

F. 波利卡普的问题

中文机器翻译题面 查看原题

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

他向协调员发送了一组 n 个问题。每个问题都有它的质量,第i个问题的质量是ai(ai可以是正数、负数或等于0)。问题按预期难度排序,但难度与质量没有任何关系。最简单的问题的索引为 1,最难的问题的索引为 n。

协调员现在的心情等于q。读完一个问题后,心情会根据问题的质量而变化。意思是协调员读到一个质量为b的问题后,将值b添加到他的心情中。协调员总是从最简单到最难的问题一一阅读,不可能改变问题的顺序。

如果协调员读完某个问题后情绪变得消极,他会立即停止阅读并拒绝该问题集。

Polycarp 希望从他的问题集中删除最少数量的问题,以使协调员的情绪在任何时刻都不是消极的。 Polycarp不确定当前协调员的情绪,但他有m个猜测“当前协调员的情绪q=bi”。

对于 m 个猜测中的每一个,找到 Polycarp 需要移除的最少问题数,以便协调员在从剩余问题中最简单的问题到最难的问题中阅读问题时,情绪始终大于或等于 0。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n ≤ 750, 1 ≤ m ≤ 200 000) — 问题集中的问题数以及对当前协调员情绪的猜测数。

输入的第二行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) - 问题的质量,按难度递增的顺序排列。

输入的第三行包含 m 个整数 b1, b2, ..., bm (0 ≤ bi ≤ 1015) – 当前协调者情绪 q 的猜测。

输出

打印 m 行,在第 i 行打印单个整数 - q = bi 问题的答案。

示例

输入 #1

6 3
8 -5 -4 1 -7 4
0 7 3

输出 #1

2
0
1