考试

题目

人要在适当的时候选择放弃。

期末考试很快就要来了，小J和小R正在有条不紊地进行复习。由于课程数量非常多，每门课程难度和对应的学分也不一样，小J和小R想做一个挑战。

现在假设一共有 N 门课程，每门课程有一个难度指数 d_i，如果通过这门课程则可以获得 w_i 个学分。

小J和小R通过努力学习共同拥有了一个学习能力 A，对于每门课程 i，如果小J和小R的学习能力 A 不低于课程难度指数 d_i，则可以获得对应的学分 w_i。

现在他们想知道如果放弃一些课程，只获得至少 W 个学分的话，他们的学习能力 A 至少需要到达多少。

现在有 Q 次询问，每次给出一个特定的学分目标 W，请你帮助小J和小R计算获得不少于 W 个学分他们的学习能力 A 至少需要到达多少。

PS：题目背景不代表主流价值观，请大家好好学习，不要放弃任何一门考试。

输入：第一行是两个正整数 N, Q；之后 N 行，每行两个正整数 d_i，w_i，表示该课程的难度以及学分；之后 Q 行，每行一个正整数 W，表示该次询问的参数。输入保证 W≤∑w_i。
输出：输出 Q 行，每行一个整数表示该次询问的答案。

样例：

4 3
2 5
3 8
4 6
6 7
5
10
20

2
3
6

提示：对于 30% 的数据，保证 N,Q≤10，d_i≤2000。对于 60% 的数据，保证 N,Q≤10。对于 100% 的数据，保证 N,Q≤2×10⁵，1≤d_i,w_i≤10⁹。

思路

复杂度分析

• 时间复杂度：
• 空间复杂度：

← 返回菜鸟的coding