分数: 400 点
问题陈述
有 N 雪橇编号 1,2,\ldots, N.
R_i 需要驯鹿拉雪橇 i.
此外,每头驯鹿最多可以拉一辆雪橇。更准确地说, \sum_{k=1}^{m} R_{i_k} 需要驯鹿拉 m 雪橇 i_1, i_2, \ldots, i_m.
找到答案 Q 以下形式的查询:
- 给你一个整数 X。确定当有雪橇时可以拉动的最大雪橇数量 X 驯鹿。
约束
- 1 \leq N, Q \leq 2 \times 10^5
- 1 \leq R_i \leq 10^9
- 1 \leq X \leq 2 \times 10^{14}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
R_1 R_2 \ldots R_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
每个查询均按以下格式给出:
X
输出
打印 Q 行。
的 树的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
4 3 5 3 11 8 16 7 1000
示例输出 1
3 1 4
当有 16 驯鹿、雪橇 1,2,4 可以拉动。
不可能拉四个雪橇 16 驯鹿,所以查询的答案 1 is 3.
示例输入 2
6 6 1 2 3 4 5 6 1 2 3 4 5 6
示例输出 2
1 1 2 2 2 3
示例输入 3
2 2 1000000000 1000000000 200000000000000 1
示例输出 3
2 0