← 返回题目列表

AtCoder · abc334_d

G. 驯鹿和雪橇

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

分数: 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