#1529. 磨合

磨合

题目描述

悠太和沙季遇到了 nn 个问题,问题的难度分别为 d1,…,dnd_1,\dots,d_n。

他们可以以任意顺序解决问题,对于准备解决的第 ii 个问题,每将难度减少 11,两人需要花费 ii 秒。将难度减少为 00 时问题被解决,他们才可以继续解决下一个问题。

如果他们正在解决第 ii 个问题(即难度尚未减少为 00),但剩余时间少于 ii 秒,他们就不能继续解决剩下的问题了,第 ii 个问题也没有解决。

他们想要知道,如果共有 tt 秒,那么最多能解决多少个问题。由于他们可能面对很多种不同情况,所以会多次改变 tt 进行询问。

输入格式

第一行输入两个整数 n,qn,q 表示问题总数和询问次数。

第二行输入 nn 个整数,表示 d1,…,dnd_1,\dots,d_n。

接下来 qq 行,每行输入一个整数表示询问的总时间 tt。

输出格式

对于每次询问输出一行一个整数表示最多能解决的问题数量。

样例

3 2
1 7 3
10
16
2
3
10 3
923 243 389 974 100 485 296 377 61 552
2403
5819
0
5
6
0

题目来源:洛谷 P12733