You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $n$ 种物品，第 $i$ 种物品的价格为 $v_i$ ，每天最多购买 $x_i$个。

有 $m$ 天，第 $i$ 天小K有$w_i$ 的钱，他会不停购买能买得起的最贵的物品。你需要求出他每天会购买多少个物品。

输入格式

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

接下来 $n$ 行每行两个整数 $v_i, x_i$。

接下来 $m$ 行每行一个整数$w_i$ 。

输出格式

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

样例

3 3
1 1
2 2
3 3
5
10
15

2
4
6

数据范围与提示

对于 $20\%$ 的数据，$n,m \leq 1000$。

另有 $40\%$ 的数据，$x_i$ = 1。

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