问题 4892 --1.礼物购买

4892: 1.礼物购买

题目描述

  有 $n$ 种物品,第 $i$ 种物品的价格为 $v_i$,每天最多购买 $x_i$ 个。
有 $m$ 天,第 $i$ 天小 K 有 $w_i$ 的钱,他会不停购买能买得起的最贵的物品。你需要求出他每天会购买多少个物品。

输入

第一行两个整数 $n,m$。
接下来 $n$ 行每行两个整数 $v_i,x_i$。
接下来 $m$ 行每行一个整数 $w_i$。

输出

输出 $m$ 行每行一个整数,第 $i$ 行表示第 $i$ 天购买的物品数量。

样例输入输出

输入#1 复制
3 3
1 1
2 2
3 3
5
10
15
输出#1 复制
2
4
6

提示

对于 $20\%$ 的数据,$n, m \leq 1000$。
对于 $40\%$ 的数据,$x_i=1$。
对于 $100\%$ 的数据,$ n,m \leq 10^5$,$1\leq v_i \leq 10^9$,$1\leq x_i \leq 10^4$,$0 \leq w_i \leq 10^{18}$。

序号 标题 作者 发表时间 费用 订购数 操作