5734. 孤星

单点时限: 2.0 sec

内存限制: 512 MB

$n(1 \leq 10^3)$ 个干员,每个干员工资为 $w_i(1 \leq w_i \leq 10^5)$,贡献值为 $v_i(1 \leq v_i \leq 10^2)$。

给出 $m(1 \leq m \leq 10^5)$次询问,每次询问:当你能承受的总工资为 $W(0 \leq W \leq 10^9)$ 时,能收获最大的贡献值是多少。

输入格式

第一行,两个整数 $n, m$。

接下来 $n$ 行,每行两个整数 $w_i, v_i$,表示每个干员的工资和贡献值。

接下来$m$行,每行一个数 $W$,表示单次询问中的可以承受的总工资。

输出格式

输出共$m$行,每行一个数表示你的答案。

样例

Input
4 3
1 2
2 1
1 1
2 3
5
1
0
Output
6
2
0

118 人解决,270 人已尝试。

168 份提交通过,共有 1863 份提交。

5.1 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 1 周,1 天前.

来源: N/A

题目标签
DP