A104882.星港补给舱调度

普及-

官方

通过率:0%

时间限制:3.00s

内存限制:256MB

题目描述

在遥远的星港“冬至号”空间站,今晚要进行一场紧急补给投送行动。空间站里停靠着 NN 个补给舱,编号为 1,2,,N1,2,\ldots,N

  • ii 个补给舱想要被成功推出并进入预定航道,需要消耗 RiR_i 单位的推进燃料。
  • 11 单位燃料最多只能用于一个补给舱,不能重复使用。
  • 只要燃料足够,可以选择任意数量任意编号的补给舱推出。

如果要同时推出 mm 个补给舱 i1,i2,,imi_1,i_2,\ldots,i_m,则至少需要燃料总量

k=1mRik\sum_{k=1}^{m} R_{i_k}

个单位,即各个推出补给舱所需的燃料之和。

由于太空中情况多变,现在空间站会收到 QQ 个询问:
给定一个整数 XX,表示当前可用燃料为 XX 单位,指挥官想知道最多能推出多少个补给舱?

输入格式

第一行输入两个整数 N,QN,Q,分别表示补给舱数量和询问次数。
第二行输入 NN 个整数表示每个补给舱所需的燃料 RiR_i
接下来 QQ 行,每行输入一个整数 XX 表示可用燃料数量。

输出格式

输出 QQ 行。第 ii 行输出第 ii 次询问的答案。

输入输出样例

  • 输入#1

    2 2
    1000000000 1000000000
    200000000000000
    1
    
    

    输出#1

    2
    0
    
  • 输入#2

    4 3
    5 3 11 8
    16
    7
    1000
    

    输出#2

    3
    1
    4
    

说明/提示

1N,Q2×1051 \le N,Q \le 2\times 10^5
1Ri1091 \le R_i \le 10^9
1X2×10141 \le X \le 2\times 10^{14}

首页